Philippe Mahenc

Marion Podesta
email: marion.podesta@univ-savoie.fr

The monopolist is not the best environmentalist's best friend: An example

Keywords: environmental quality, public good, price discrimination, tying JEL classi…cation: D42, L12, Q5

This letter addresses the second-degree price discrimination issue when a monopolized product is tied with environmental quality. The monopolist may degrade environmental quality too much when marginal valuations of environmental quality and the good itself are positively related across consumers.

Introduction

The famous discussion of railroad tari¤s for passenger tra¢c in [START_REF] Dupuit | On tolls and transport charges[END_REF] suggests that a monopolist …nds it advantageous both to degrade the quality intended for the poor and enhance that intended for the rich in order to discriminate prices.

What the company is trying to do is prevent the passengers who can pay the second-class fare from traveling third-class; it hits the poor, not because it wants to hurt them, but to frighten the rich. . . And it is again for the same reason that the companies, having proved almost cruel to the third-class passengers and mean to the second-class ones, become lavish in dealing with …rst-class passengers. Having refused the poor what is necessary, they give the rich what is super ‡uous. 1 Most of the formal models stemming from [START_REF] Mussa | Monopoly and product quality[END_REF] have emphasized that imperfect discrimination leads to a degradation in the quality of the product o¤ered to the consumers with a low willingness-to-pay. This makes the product less attractive to consumers with a high willingness-to-pay, which allows the monopolist to segment the market. One exception is [START_REF] Srinagesh | Quality distortion by a discriminating monopolist[END_REF] who demonstrate the idea that quality discrimination can also lead to providing too much quality to the consumers with a high willingness-to-pay. The common intuition underlying these results is that asymmetric information creates a negative externality for the monopolist. Internalizing this externality requires preventing consumers of one type from switching to the quality intended for another type.

In this literature, quality is treated as an excludable characteristic of the good, that is, the user of the good tied2 with one level of quality can be excluded from consuming the good tied with another level of quality. If however quality is environmental, than no one can be prevented from enjoying the level of environmental quality o¤ered to the users of the good, whatever the quantity purchased. Our purpose is to examine the provision of environmental quality by a discriminating monopolist in a model that treats environmental quality not only as a vertical attribute3 of the monopolized good, but also as a non-excludable characteristic.

In our model, consumer preferences are such that there is a positive correlation between the valuation of the tying good and the tied environmental quality, as illustrated for instance by a ski resort. Indeed, we expect a consumer with a high willingness-to-pay for the ski resort to be more environmentally friendly too. In this note, we show that the monopolist may provide an ine¢ciently low level of environmental quality given the price-quantity combinations o¤ered to consumers. This result departs from the view popularized by [START_REF] Buchanan | External diseconomies, corrective taxes and market structure[END_REF] that a polluting monopolist behaves in a more e¢cient way than does a polluting competitive …rm because the output reduction due to the exercise of monopoly power scales down the harm done to the environment (see also [START_REF] Barnett | The Pigouvian tax rule under monopoly[END_REF], for more on this point).

The model

The monopolist supplies a good or a service tied with an environmental service to the consumer. This service provides environmental quality at some level measured by the index e. Environmental quality will be treated as a public good that is not excludable. The level of environmental quality is set by the monopolist, i.e., e is a choice variable. If, for instance, the monopolist provides recreational activities by a lake, he will also control the quality of water and the cleanliness of the banks. Similarly, the choice of environmental quality in a ski resort may be determined by a number of variables including the fuel-e¢ciency of ski lifts, the ski resort location and its blending into the natural surroundings.

The monopolist faces a demand composed of two types of consumers di¤erentiated by their taste for the good. There is no exogenous signal of each consumer type i = 1; 2. The proportion of consumer type i in the market place is i .

Assume a quasi-linear utility function for consumers of type i

u i = b i (q i ; e) + x i (1)
where x i is consumption of the numeraire commodity, q i is the consumption of the good tied with environmental quality e, and b i (0; e) = 0. Our speci…cation of preferences follows [START_REF] Carbone | Evaluating policy interventions with general equilibrium externalities[END_REF] in that the environmental externality is not separable from private consumption. This captures an environmental feedback on demand: changes in environmental quality do in ‡uence the consumption behavior.

We normalize the price of numeraire to equal 1, and we let t i denote total spending on the quantity of good purchased by consumer i from the monopolist. Consumer i's budget constraint is

t i + x i = r i (2)
where r i is the consumer's initial endowment of the numeraire. We can write net utility as

u i = b i (q i ; e) t i + r i (3)
Partial derivatives @b i =@q i = P i (q i ; e) and @b i =@e represent, respectively, consumer i's marginal willingness-to-pay (MWTP) for the good and his MWTP for environmental quality.

Assumptions 1: For all (q; e), b 1 (q; e) < b 2 (q; e) and @b 1 =@q = P 1 (q; e) < @b 2 =@q = P 2 (q; e).

High-demand consumers 2 are willing to pay more than low-demand consumers 1 for both a given amount of the good and environmental quality. Moreover, high-demand consumers' MWTP exceeds that of low-demand consumers.

We will specialize the model so that b i (q; e) = eq ( i q=2), where i represents the taste for the good, with 1 < 2 . This speci…cation extends [START_REF] Mussa | Monopoly and product quality[END_REF] to preferences de…ned over a public good. MWTPs are P i (q; e) = e ( i q) for the good and @b i =@e = q ( i q=2) for environmental quality. Note that, for all q such that P i (q; e) > 0, we have @b i =@e > 0, that is, both types of consumers 1 and 2 prefer the good to be more environmentally friendly. This follows the recent approach in environmental literature that considers environmental quality as a vertical attribute of the good. In addition, @b 1 =@e < @b 2 =@e means that the high-demand consumers are more concerned about environmental quality than the low-demand consumers. This …ts in with outdoor leisure activities such as skiing, sailing, walking or …shing since the more people are fond of such activities, the more they feel concerned about the environment.

Let the cost of producing one unit of the good tied with environmental quality e be c(e), where c(e) is an increasing and convex function of e. This implies that a cleaner good is more costly to produce: the resources allocated by the monopolist to pollution abatement and wastes cleanup raise the production costs. To make things interesting, we will assume that supplying the good to any type of consumer on the market is socially e¢cient, that is,

Assumption 2: 1 c(e) e > 0.

Social optimum

Given that the total amount of the numeraire available for distribution among consumers is

2 X i=1 i r i c(e) 2 X i=1 i q i ,
the optimization problem of the benevolent planner is max q 1 ;q 2 ;e W (q 1 ; q 2 ; e)

2 X i=1 i b i (q i ; e) + 2 X i=1 i r i c(e) 2 X i=1 i q i
Assuming an interior solution (q 1 ; q 2 ; e ), conditions for a social optimum are

P i (q i ; e ) = c(e ); i = 1; 2 (4) 2 X i=1 i @b i =@e = c 0 (e ) 2 X i=1 i q i (5)
From (4), social e¢ciency requires that the low-and high-demand consumers have the same MWTP for the good, equal to the marginal cost of producing the good. Moreover, by condition (5), the weighted sum of MWTPs for environmental quality equals the marginal cost of providing this quality.

First-degree price discrimination

Suppose …rst that the monopolist perfectly observes the type of each consumer. The monopolist wants to o¤er consumers i = 1; 2 some price, quantity and environmental quality combination (t i ; q i ; e) that yields the maximum pro…t. This combination is a take it or leave it o¤er: consumer i can either pay t i , consume q i and enjoy environmental quality e, or buy and pay nothing.

The pro…t maximization problem of the monopolist is max t 1 ;t 2 ;q 1 ;q 2 ;e 2 X i=1 i (t i c(e)q i ) such that b i (q i ; e) t i 0; i = 1; 2 (IR). Individual rationality constraints (IR) require that each type of consumer be willing to purchase. Equality will hold for each one since the monopolist wants t i to be as large as possible.

b i (q i ; e) t i = 0; i = 1; 2 (6) Substituting from the constraints, we get exactly the same optimization problem as that faced by the benevolent planner. Note that the monopolist behaves in a socially desirable way here because all consumer surplus goes to the monopolist.

Second-degree price discrimination

Suppose now that the monopolist cannot tell the consumers apart. Due to asymmetric information, consumers may have the temptation to choose the "wrong" combination of price, quantity, and environmental quality, i.e., the one not intended for their type. In addition to previous individual rationality constraints, two further incentive compatibility constraints, (IC i ) ; i = 1; 2, now bind the monopolist. The problem facing the monopolist is max t 1 ;t 2 ;q 1 ;q 2 ;e 2

X i=1 i (t i c(e)q i ) (7)
s:t:

8 > > < > > :
b 1 (q 1 ; e) t 1 b 1 (q 2 ; e) t 2 (IC 1 ) b 2 (q 2 ; e) t 2 b 2 (q 1 ; e) t 1 (IC 2 ) b 1 (q 1 ; e) t 1 0 (IR 1 ) b 2 (q 2 ; e) t 2 0 (IR 2 )

As a preliminary result, we demonstrate that the output quantities now supplied to both types of consumers verify q m 1 q m 2 . Adding (IC 1 ) to (IC 2 ) yields b 1 (q 1 ; e) b 2 (q 1 ; e) b 1 (q 2 ; e) b 2 (q 2 ; e):

From Assumptions 1, we have @b 1 =@q @b 2 =@q < 0. Thus, inequality (8) implies q m 1 q m 2 . Let us now show that inequalities (IC 2 ) and (IR 1 ) are binding constraints in the solution of the monopolist's problem.

As usual, the proof is by contradiction. Indeed, suppose it is not so. Then the monopoly could either raise t 2 or (and) t 1 by a small amount so that market segmentation remains unchanged, i.e., the high-demand consumer is still worse o¤ switching to the combination (t 1 ; q 1 ; e) intended for the low-demand consumer, and the latter still accepts (t 1 ; q 1 ; e). This would increase the monopolist's pro…t, thereby leading to a contradiction: such an increase cannot happen in a pro…t-maximizing solution.

Hence, the binding constraints (IR 1 ) and (IC 2 ) yield b 1 (q 1 ; e) = t 1 and (9) t 1 t 2 = b 2 (q 1 ; e) b 2 (q 2 ; e): [START_REF] Mussa | Monopoly and product quality[END_REF] In the solution of the pro…t-maximizing problem, the monopoly extracts the whole surplus of the low-demand consumer, as shown by [START_REF] Ekelund | Price discrimination and product di¤erentiation in economic theory: An early analysis[END_REF]. Moreover, equality [START_REF] Mussa | Monopoly and product quality[END_REF] says that highdemand consumers are charged the highest price that just induces their consumption of the quantity directed at them. Turning now to constraints (IR 2 ) and (IC 1 ), we show that they can be eliminated as being nonbinding.

First, (IR 1 ) and (IC 2 ) immediately imply (IR 2 ) since b 1 (q 1 ; e) < b 2 (q 1 ; e). Hence, the high-demand consumer obtains here an extra surplus u 2 r 2 > 0 compared to the …rst-best solution.

Second, using [START_REF] Mussa | Monopoly and product quality[END_REF], the constraint (IC 1 ) can be rewritten b 1 (q 1 ; e) b 1 (q 2 ; e) b 2 (q 1 ; e) b 2 (q 2 ; e) = t 1 t 2 :

From Cauchy's generalized mean value theorem, there exists at least one q with q 1 < q < q 2 such that b 1 (q 1 ; e) b 1 (q 2 ; e) @b 1 (q)=@q = b 2 (q 1 ; e) b 2 (q 2 ; e) @b 2 (q)=@q :

We know from Assumptions 1 that @b 1 =@q < @b 2 =@q. As moreover q 1 q 2 , we have b 2 (q 1 ; e) b 2 (q 2 ; e) 0, and so [b 2 (q 1 ; e) b 2 (q 2 ; e)] @b 1 (q)=@q @b 2 (q)=@q > b 2 (q 1 ; e) b 2 (q 2 ; e):

Using [START_REF] Mussa | Monopoly and product quality[END_REF], this inequality can be rewritten [b 2 (q 1 ; e) b 2 (q 2 ; e)] P 1 (q; e) P 2 (q; e) > t 1 t 2 :

Furthermore (12) implies b 1 (q 1 ; e) b 1 (q 2 ; e) = [b 2 (q 1 ; e) b 2 (q 2 ; e)] P 1 (q; e) P 2 (q; e) :

private information induces the high-demand consumer to switch to the monopolist's o¤er of the combination designed for the low-demand consumer. This masquerade reduces the high-demand consumer's valuation of environmental quality from @b 2 (q 2 ; e)=@e to @b 2 (q 2 ; e)=@e (@b 2 (q 1 ; e)=@e @b 1 (q 1 ; e)=@e). As can be seen in the left-hand side of (19), the monopolist internalizes the inclination of high-demand consumers to pay less for environmental quality than they are actually willing to pay. This yields level of environmental quality which is too low. Proposition 1. If q m 1 < q 1 and q m 2 = q 2 , then if 2 , the monopolist removes the low-demand consumers from the market and provides the socially e¢cient level of environmental quality; if 0 < 2 < , the monopolist serves both types of consumers and underprovides environmental quality.

Following the evocative expression of Dupuit (1849), the monopolist "hits the poor" twice when their group is so large that 2 < . First, the monopolist reduces the output quantity in the combination proposed to low-demand consumers, in order to make it unattractive to high-demand consumers. Second, the monopolist o¤ers an ine¢ciently low level of environmental quality, thereby "hitting the rich" too. The reason is that the monopolist underestimates the high-demand consumers' valuation of environmental quality by internalizing their tendency to masquerade as low-demand consumers. This result may explain why the environment is not su¢ciently protected in very popular sites supplying recreational activities. If, for instance, the environmental indicator is how the buildings and infrastructure of a ski resort melt into the background, laxity on this point is more likely to be observed in places crowded with low-demand consumers. When the group of high-demand consumers is so large that 2 , the monopolist deters lowdemand consumers from purchasing the good and sets the e¢cient level of environmental quality.

Tying is the practice requiring the consumer of one good (or service) to also purchase a second good (or service).

This assumption follows the recent approach in the environmental literature. It can be found for instance in[START_REF] Arora | Toward a theoretical model of voluntary overcompliance[END_REF],[START_REF] Bansal | Tax/subsidy policies in the presence of environmentally aware consumers[END_REF],[START_REF] Amacher | Environmental quality competition and eco-labeling[END_REF] and[START_REF] André | Strategic quality competition and the Porter Hypothesis[END_REF].

We …nally conclude from (14) that b 1 (q 1 ; e) b 1 (q 2 ; e) > t 1 t 2 :

(16) Therefore, inequality (IC 1 ) will be a nonbinding constraint. This simpli…cation in the number of relevant constraints leaves us with both binding constraints (IC 2 ) and (IR 1 ). Substituting (9) and (10) into [START_REF] Carbone | Evaluating policy interventions with general equilibrium externalities[END_REF], we obtain a reduced program max q 1 ;q 2 ;e (q 1 ; q 2 ; e). Assuming an interior solution (q m 1 ; q m 2 ; e m ), the …rst-order conditions based on the e¤ective constraints are P 2 (q m 2 ; e m ) = c(e m ) (17)

1 @b 1 (q m 1 ; e m )=@e + 2 @b 2 (q m 2 ; e m )=@e 2 (@b 2 (q m 1 ; e m )=@e @b 1 (q m 1 ; e m )=@e)

= c 0 (e m )( 2 q m 2 + 1 q m 1 ):

Conditions (17) and (18) yield the familiar result of monopolistic imperfect quantity discrimination: the high-demand consumer purchases the socially optimal amount of the good, while the low-demand consumer purchases an ine¢ciently small amount of the good. In the words of Dupuit (1849), the monopolist "hits the poor" with a reduction in quantity because the low-demand consumer su¤ers relatively less from reduced quantity than the high-demand consumer. This makes the combination (t m 1 ; q m 1 ; e m ) less attractive to the high-demand consumer.

Using the speci…cation b i (q; e) = eq ( i q=2), we obtain from (18)

c(e m ) e m : (20)

Observe that 2 must be su¢ciently low to get the existence of an interior solution for q m 1 . More precisely, q m 1 > 0 only if 2 < 1 c(e m )=e m 2 c(e m )=e m . When the proportion of high-demand consumers is above , the monopolist is worse o¤ attracting low-demand consumers to the market. Given q m 1 = 0, the monopolist provides the socially e¢cient level of environmental quality to high-demand consumers since condition (19) can be rewritten @ (q m 1 ; q m 2 ; e m ) @e = @W (q m 1 ; q m 2 ; e m ) @e = 0:

Suppose now 2 < , so that low-demand consumers are not excluded from the market. From (4), we know that

e m . From (20), second-degree price discrimination involves a 2 1 ( 2 1 ) reduction in the quantity intended for low-demand consumers. If we specialize the model as previously mentioned, we have @b 2 (q 1 ; e)=@e @b 1 (q 1 ; e)=@e = q 1 ( 2 1 ) > 0. Substituting this into (19), we have @ (q m 1 ; q m 2 ; e m ) @e = @W (q m 1 ; q m 2 ; e m ) @e 2 q m 1 ( 2 1 ) = 0:

Thus, q m 1 > 0 implies @W (q m 1 ;q m 2 ;e m ) @e > 0, and so, given (q m 1 ; q m 2 ), the monopolist provides an ine¢ciently low level of environmental quality. The intuition is that consumer's


Jean-Charles Lamirel
email: jean-charles.lamirel@inria.fr

Pascal Cuxac
email: pascal.cuxac@inist.fr

Raghvendra Mall
email: raghvendra.mall@research.iiit.ac.in

A new efficient and unbiased approach for clustering quality evaluation

Traditional quality indexes (Inertia, DB, . . . ) are known to be method-dependent indexes that do not allow to properly estimate the quality of the clustering in several cases, as in that one of complex data, like textual data. We thus propose an alternative approach for clustering quality evaluation based on unsupervised measures of Recall, Precision and F-measure exploiting the descriptors of the data associated with the obtained clusters. Two categories of index are proposed, that are Macro and Micro indexes. This paper also focuses on the construction of a new cumulative Micro precision index that makes it possible to evaluate the overall quality of a clustering result while clearly distinguishing between homogeneous and heterogeneous, or degenerated results. The experimental comparison of the behavior of the classical indexes with our new approach is performed on a polythematic dataset of bibliographical references issued from the PASCAL database.

Introduction

The use of classification methods is mandatory for analyzing large corpus of data as it is the case in the domain of scientific survey or in that of strategic analyzes of research. While carrying out a classification, one seeks to build homogeneous groups of data sharing a certain number of identical characteristics. Furthermore, the clustering, or unsupervised classification, makes it possible to highlight these groups without prior knowledge on the treated data. A central problem that then arises is to qualify the obtained results in terms of quality: a quality index is a criterion which indeed makes it possible altogether to decide which clustering method to use, to fix an optimal number of clusters, and to evaluate or to develop a new method. Even if there exist recent alternative approaches [START_REF] Bock | Probability model and hypothese testing in partitionning cluster analysis[END_REF] [8] [START_REF] Halkidi | On clustering validation techniques[END_REF], the most usual indexes employed for the evaluation of the quality of clustering are mainly distance-based indexes relying on the concepts of intra cluster inertia and inter-cluster inertia [START_REF] Lebart | Traitement des données statistiques[END_REF]:

-Intra-cluster inertia measures the degree of homogeneity between the data associated with a cluster. It calculates their distances compared to the reference point representing the profile of the cluster. It can be defined as:

Intra = 1 |C| c∈C 1 |c| d∈c p c -p d 2
where C represents the set of clusters associated to the clustering result, d represents a cluster associated data and p x represents the profile vector associated to the element x.

-Inter-clusters inertia measures the degree of heterogeneity between the clusters. It calculates the distances between the reference points representing the profiles of the various clusters of the partition.

Inter = 1 |C| 2 -|C| c∈C c ′ ∈C,c ′ =c p c -p c ′ 2
Thanks to these two quality indexes or their adaptations, like the Dunn index [START_REF] Dunn | Well Separated clusters and optimal fuzzy partitions[END_REF], the Davies-Bouldin index [START_REF] Davies | A cluster separation measure[END_REF], or the Silhouette index [START_REF] Rousseeuw | Silhouettes: a graphical aid to the interpretation and validation of cluster analysis[END_REF], a clustering result is considered as good if it possesses low intra-clusters distances as compared to its inter-clusters distances. However, it has been shown in [START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF] that the distance based indexes are often strongly biased and highly dependent on the clustering method. They cannot thus be easily used for comparing different methods. Moreover, as Forest also pointed out [START_REF] Forest | Application de techniques de forage de textes de nature prédictive et exploratoire à des fins de gestion et danalyse thématique de documents textuels non structurés[END_REF], the experiments on these indexes in the literature are often performed on unrealistic test corpora constituted of low dimensional data and embedding a small number of potential classes. As an example, in their reference paper Milligan and Cooper [START_REF] Milligan | An Examination of Procedures for Determining the Number of Clusters in a Data Set[END_REF] compared 30 different methods for estimating the number of clusters relying only on simulated data described in a low dimensional Euclidean space. Nonetheless, using Reuters test collection, it has been shown by Kassab and Lamirel [10] that aforementioned indexes are often properly unable to identify an optimal clustering model whenever the dataset is constituted by complex data that must be represented in a both highly multidimensional and sparse description space, as it is often the case with textual data. To cope with such problems, our own approach takes its inspiration both from the behavior of symbolic classifiers and from the evaluation principles used in Information Retrieval (IR). Our Recall/Precision and F-measures indexes exploit the properties of the data associated to each cluster after the clustering process without prior consideration of clusters profiles [START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF]. Their main advantage is thus to be independent of the clustering methods and of their operating mode. However, our last experiments highlighted that these new quality indexes did not make it possible to clearly distinguish between homogeneous results of clustering and heterogeneous, or degenerated ones [START_REF] Ghribi | Mesures de qualité de clustering de documents : Prise en compte de la distribution des mots-clés[END_REF]. After presenting our original quality indexes, we thus describe hereafter some of their extensions which make it possible to solve the aforementioned problem. We then experimentally show the effectiveness of our extended approach, as compared to classical distance-based approach, for discriminating between the results provided by three different clustering methods which have been applied on a polythematic documentary corpus containing various bibliographic records issued from the PASCAL CNRS scientific database.

2 Unsupervised Recall Precision F-measure indexes

Overall clustering quality estimation

In IR, the Recall R represents the ratio between the number of relevant documents which have been returned by an IR system for a given query and the total number of relevant documents which should have been found in the documentary database [START_REF] Salton | The SMART Retrieval System: Experiments in Automatic Document Processing[END_REF]. The Precision P represents the ratio between the number of relevant documents which have been returned by an IR system for a given query and the total number of documents returned for the said query. Recall and Precision generally behave in an antagonist way: as Recall increases, Precision decreases, and conversely. The F function has thus been proposed by Van Rijsbergen [START_REF] Van Rijsbergen | Information Retrieval[END_REF] in order to highlight the best compromise between these two values. It is given by:

F = 2(R * P ) R + P (1)
Based on the same principles, the Recall and Precision indexes which we introduce hereafter evaluate the quality of a clustering method in an unsupervised way1 by measuring the relevance of the clusters content in terms of shared properties, or features. In our further descriptions, a cluster content is supposed to be represented by the data associated with this latter after the clustering process and the descriptors (i.e. the properties or features) of the data are supposed to be weighted by values within the range [0,1].

Let us consider a set of clusters C resulting from a clustering method applied on a set of data D, the local Recall (Rec) and Precision (Prec) indexes for a given property p of the cluster c can be expressed as:

Rec c (p) = |c * p | |D * p | , P rec c (p) = |c * p | |c|
where the notation X * p represents the restriction of the set X to the set members having the property p.

Then, for estimating the overall clustering quality, the averaged Macro-Recall (R M ) and Macro-Precision (P M ) indexes can be expressed as:

R M = 1 |C| c∈C 1 |S C | p∈S C Rec c (p), P M = 1 |C| c∈C 1 |S C | p∈S C P rec c (p) (2)
where S c is the set of peculiar properties of the cluster c, which can be defined as:

S c =    p ∈ d, d ∈ c|W p c = M ax W p c ′ c ′ ∈C    (3)
and where C represents the peculiar set of clusters extracted from the clusters of C, which verifies:

C = {c ∈ C|S c = ∅}
and, finally:

W p c = d∈c W p d c ′ ∈C d∈c ′ W p d ( 4
)
where W p x represents the weight of the property p for element x.

It can be demonstrated (see [START_REF] Lamirel | New classification quality estimators for analysis of documentary information: application to patent analysis and web mapping[END_REF] for more details) that if both values of averaged Recall and Precision reach the unity value, the peculiar set of clusters C represents a Galois lattice. Therefore, the combination of this two measures enables to evaluate to what extent a numerical clustering model can be assimilated to a Galois lattice natural classifier.

Macro-Recall and Macro-Precision indexes defined by (Eq. 2) can be considered as cluster-oriented measures because they provide average values of Recall and Precision for each cluster. They have opposite behaviors according to the number of clusters. Thus, these indexes permit to estimate in a global way an optimal number of clusters for a given method and a given dataset. The best data partition, or clustering result, is in this case the one which minimizes the difference between their values (see Figure 1B). However, similarly to the classical distance-based indexes, their main defect is that they do not permit to detect degenerated clustering results, whenever those jointly include a small number of heterogeneous or "garbage" clusters of large size and a big number of "chunk" clusters of very small size [START_REF] Ghribi | Mesures de qualité de clustering de documents : Prise en compte de la distribution des mots-clés[END_REF]. To correct that, we propose to construct complementary property-oriented indexes of Micro-Recall and Micro-Precision by averaging the Recall/Precision values of the peculiar properties independently of the structure of the clusters:

R m = 1 |L| c∈C,p∈Sc Rec c (p), P m = 1 |L| c∈C,p∈Sc P rec c (p) (5)
where L represents the size of the data description space.

It is possible to refer not only to the information provided by the indices M icro-P recision and M icro-Recall, but to the calculation of the M icro-P recision operated cumulatively. In the latter case, the idea is to give a major influence to large clusters which are most likely to repatriate the heterogeneous information, and therefore, by themselves, lowering the quality of the resulting clustering. This calculation can be made as follows:

CP m = i=|c inf |,|csup| 1 |Ci+| 2 c∈Ci+,p∈Sc |cp| |c| i=|c inf |,|csup| 1
Ci+ (6)
where C i+ represents the subset of clusters of C for which the number of associated data is greater than i, and:

inf = argmin ci∈C |c i |, sup = argmax ci∈C |c i | (7)

Cluster labeling and content validation

Complementary to overall clustering model evaluation, the role of clusters labeling is to highlight the peculiar characteristics or properties of the clusters associated to a clustering model at a given time. Labeling can be thus used both for visualizing or synthesizing clustering results [START_REF] Lamirel | Novel labeling strategies for hierarchical representation of multidimensional data analysis results[END_REF] and for validating or optimizing learning of a clustering method [START_REF] Attik | Clustering Quality Measures for Data Samples with Multiple Labels[END_REF]. It can rely on endogenous data properties or on exogenous ones. Endogenous data properties represent the ones being used during the clustering process. Exogenous data properties represent either complementary properties or specific validation properties. Some label relevance indexes can be derivated from our former quality indexes using a probabilistic approach. The Label Recall L-R derives directly from Eq. 4. It is expressed as:

L - c R(p) = W p c (8)
The Label Precision P-R can be expressed as:

L - c P (p) = d∈c W p d p ′ ∈d,d∈c W p d (9)
Consequently, the set of labels L c that can be attributed to a cluster c can be expressed as the set of endogenous or exogenous cluster data properties which maximize the Label F-measure that combines the Label Recall (Eq. 8) and Label Precision (Eq. 9) in the same way than the supervised F-measure described by (Eq.1) would do. As soon as Label Recall is equivalent to the conditional probability P (c|p) and Label Precision is equivalent to the conditional probability P (p|c), this former labeling strategy can be classified as an expectation maximization approach with respect to the original definition given by Dempster and al. [START_REF] Dempster | Maximum likelihood for incomplete data via the em algorithm[END_REF].

Experimentation and Results

To illustrate the behavior of our new quality indexes, and to compare it to the one of the classical inertia indexes, our test dataset is build up from is a set of bibliographic records resulting from the INIST PASCAL database and covering one year of research performed in the French Lorraine area. The structure of the records makes it possible to distinguish the titles, the summaries, the indexing keywords and the authors as representatives of the contents of the information published in the corresponding article. In our experiment, the research topics associated with the keywords field are solely considered. Our test dataset represents a dataset of 1341 records. A frequency threshold of 3 being finally applied on the index terms, it resulted in a data description set of 889 indexing keywords. These keywords cover themselves a large set of different topics (as far one to another as medicine from structural physics or forest cultivation . . . ). Moreover, they comprise a high ratio of polysemic forms (like age, stress, structure, . . . ) that are used in the context of many different topics. The resulting experimental dataset can thus be considered as a complex dataset for clustering.

To carry out the clustering, we exploited in parallel the SOM fixed topology neural method [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF], the Neural Gas (NG) free topology neural method [START_REF] Martinetz | A neural gas network learns topologies[END_REF] and the classical K-means method [START_REF] Macqueen | Some methods of classification and analysis of multivariate observations[END_REF]. For each method, we do many different experiments letting varying the number of clusters from 9 to 324 clusters, employing the size of an increasing square SOM grid as a basic stepping strategy. In the next paragraphs, for the sake of clarity, we dont specifically report the results of K-means because they are similar to those of NG.

The analysis of the results performed by an expert showed that only the SOM method provided homogeneous clustering results on this dataset. Hence, in the case of the NG (or K-means) method, the analyst highlighted the presence of "garbage" clusters attracting most of the data in parallel with "chunk" clusters representing either marginal groups or unformed topics. This behavior, that corresponds to the case of degenerated clustering results due to the dataset clustering complexity, can also be confirmed when one looks to the labels that can be extracted from the clusters in an unsupervised way using the expectation maximization methodology described in section 2.2. Hence, it permits to highlight that the NG mainly produced a "garbage" cluster with very big size that collects more than 80% of the data and attracts (i.e. maximize) many kinds of different labels (730 labels among a total of 889). Conversely, the good results of the SOM method can be confirmed in the same way. Hence, cluster labels extraction also shows that this latter method produces different clusters of similar size attracting semantically homogeneous labels groups, which figure out the main research topics covered by the analyzed dataset.

On the one hand, the results presented in Figure 1A illustrate the fact that the classical indexes of inertia have an unstable behavior which does not make it possible to clearly identify an optimal number of clusters in both contexts of SOM and NG methods. On the other hand, it also appears in Figure 1B that the behavior of the Macro-Recall/Precision indexes is stable and makes it possible to identify an optimal number of clusters in all cases. Indeed, this optimal clusters number can be found out at the break-even point between the Macro-Recall and the Macro-Precision values (i.e. 100 clusters for NG and 256 clusters for SOM in Figure 1B).

Nonetheless, none of these former groups of indexes, whenever it is solely considered, permits to correctly estimate the quality of the results. Those do not make it possible in particular to discriminate between homogeneous results of clustering (SOM) and degenerated ones (NG or K-means). In both cases, they even present the important defect to privilege this last family of results, illustrating a contradictory behavior (i.e. the worst results are identified as the best, and conversely). In the case of degenerated results, one potential explanation of the better values of aforementioned indexes is that the joint presence of a big amount of "chunk" clusters which are both coherent and necessarily distant of a small amount of "garbage" clusters can compensate, and even hide, the imprecision of these latter because of the cluster-based averaging process performed by those indexes. In the context of our approach, the detection of degenerated clustering results can although be achieved in two different ways:

The first way is the joint exploitation of the values provided by our Macroand Micro-Precision indexes, as it is shown in Figure 2A and Figure 2B. The Micro-Recall/Precision indexes have general characteristics similar to the Macro-Recall/Precision. However, by comparing their values with those of the latter indexes, it becomes possible to identify heterogeneous results of clustering. Indeed, in this last case, the Precisions of the clusters of small size will not compensate for any more those of the clusters of big size, and the imprecise properties present in the latter, if they prove to be heterogeneous, will have a considerable effect on the Micro-Precision. Thus, in the case of NG the differences between the values of Micro-and Macro-Precision are increasingly more important than in the case of SOM, whatever the considered number of clusters (Figure 2A). It proves that the peculiar properties of the clusters in the partitions generated by NG (or K-means) are largely less precise than those of the clusters produced by SOM. The analysis of the evolution of the Micro-Precision curves of the two methods according to the size of the clusters (Figure 2B) permits to clearly highlight that this phenomenon affect more particularly the NG clusters of big size.

A second way to appropriately estimate the quality of clustering results is thus to directly exploit the results provided by the indexes of Cumulated Micro-Precision (CP m ) that focuses on the imprecision of big sized clusters (Eq. 10). In the case of NG, the value of Cumulated Micro-Precision remains very low, regardless to the expected number of clusters (Figure 3A). This is mainly due to the influence of Micro-Precision of "garbage" clusters with significant size that can never be split into smaller groups by the method. In a complementary way, whatever the method considered, the index of Cumulated Micro-Precision ensures accurate monitoring of the quality depending on the chosen configuration in terms of number of clusters. In the case of SOM, the quality loss occurring for some grid sizes (eg. 244 clusters model, corresponding to a 12x12 grid, in Figure 3A) that induces the formation of large heterogeneous clusters is accurately characterized by highly decreasing values of this index. Figure 3B finally illustrates the interest of correcting the Cumulated-Micro-Precision index (Eq. 10) by factorizing it with the ratio of non empty clusters for detecting the optimal number of clusters. The curve associated with this corrected index shows a plateau whose starting point (eg. 256 clusters model in Figure 4B) permits to identify the most efficient partition. In this case, such point highlights that no quality progress can be obtained with higher number of clusters. This information is compliant with the one obtained with Macro-Recall and Macro-Precision indexes (see Figure 1B and associated comments) and thus validates the choice of such point as the characteristic value of the clustering results for a given method.

Conclusion

We have proposed a new approach for the evaluation of the quality of clustering based on the exploitation of the properties associated with the clusters through the indexes of Macro-and Micro-Recall/Precision and their extensions. We have shown the advantage of this approach with respect to traditional of evaluation of clustering quality based on distances, at the same time, by justifying its theoretical basis through its relationship with the symbolic classification approaches, and by showing practical results for the optimization of the number of clusters of a given method. Our experimental have been achieved in a realistic context constituted by a complex textual dataset. In such context, we have shown that our new indexes can accurately assess the global quality of a clustering result while giving the additional possibility to distinguish clearly between homogeneous and degenerated clustering results. We have also shown that our approach can apply to the comparison of the results issued from different methods, as well as to the fine-grained analysis of the results provided by a given method, avoiding in both cases to lead to clustering quality misinterpretation. We have finally shown, through our experiments, the additional capabilities of our approach for synthesizing and labeling the clusters content and we have yet proved their usefulness for a better understanding of the nature of the clustering results. We more specifically tried out our methodology on textual data, but it proves sufficiently general to be naturally applicable on any other type of data, whatever is their nature.

Fig. 1 .

 1 Fig. 1. Inertia (1A) and Macro Recall Precision (1B) indexes evolution as regards to the number of clusters.

Fig. 2 .

 2 Fig. 2. Evolution of the values of the Micro-Precision (MIC-P) and Macro-Precision (MAC-P) indexes according to the number of clusters (2A) and their size (2B).

Fig. 3 .

 3 Fig. 3. Evolution of the values of Cumulated Micro-Precision (3A) and Corrected Cumulated Micro-Precision (3B) indexes according to the number of clusters.

Conversely to classical Recall and Precision indexes that are supervised.


Amel Bennaceur

Arosha Bandara

Michael Jackson

Wei Liu

Lionel Montrieux

Thein Than Tun

Yijun Yu

Bashar Nuseibeh

Requirements-Driven Mediation for Collaborative Security

Keywords: Security requirements, mediation, collaborative adaptation D.2 [Software Engineering]: Requirements/Specifications; K.6 [Management of Computing and Information Systems]: Security and Protection

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

INTRODUCTION

As our reliance on digital, connected devices increases, so does our need for security. Secure systems must provide the necessary capabilities to protect assets from intentional harm. These systems rely on an explicit definition of their security requirements to describe precisely which actions in a system are allowed and which ones are prohibited [START_REF] Tanenbaum | Distributed systems: principles and paradigms[END_REF]. Once security requirements are specified, it becomes possible to concentrate on the security controls by which these security requirements can be satisfied.

The high-degree of dynamism and the inherent heterogeneity of mobile and ubiquitous computing environments make security requirements hard to satisfy. First, the components and the assets of the system might be mobile (e.g., smartphones and personal trackers), making the boundary of the system ill defined and uncertain. These components are also often developed independently, and may only be accessed through particular interfaces and specific protocols. For example, the protocol used by a lighting system is likely to be different from that used by a surveillance camera for video recoding. In addition, the physical environment must also be taken into account. For example, a surveillance camera may only be able to capture video when there is enough light. Therefore, the light may need to be turned on when the camera needs to be operated in the dark. It is difficult to design and develop the security controls necessary to protect assets when the operational context is continually changing, and no exact assumptions about the environment can be made.

The complexity of security controls necessary to satisfy security requirements in mobile and ubiquitous computing environments means that they may be unlikely to be implemented by a single component, or even by multiple components in isolation. For example, a smart home may be equipped with a whole range of electronic devices that can help keep the homeowner and their property safe from intruders. If the light is switched on without the door being opened, this can indicate an intrusion and should trigger the alarm. The lighting system, the door lock, and the alarm each provides a specific capability, which put together allows the realisation of the security control necessary to protect the house. In this paper we propose a novel framework for collaborative security that leverages the capabilities of multiple components available in the environment in order to deploy the necessary security controls and satisfy security requirements. To realise collaborative security, we must be able to answer several questions:

• How do we capture, represent, and reason about the capabilities of components in ubiquitous computing environments?

• Which components should collaborate to satisfy security requirements?

• How do we make components collaborate?

• Can we ensure that the collaboration satisfies properties such as correctness, safety, and minimality?

In taking initial steps in answering these questions, we build upon adaptive security [START_REF] Salehie | Requirements-driven adaptive security: Protecting variable assets at runtime[END_REF] and collaborative adaptation [START_REF] Yang | Enabling collaborative adaptation across legacy components[END_REF]. The former focuses on identifying the security controls necessary to keep security requirements satisfied despite changes in the environment. The latter concentrates on the mechanisms necessary to make multiple components collaborate. However, this collaboration is often hampered by differences in the implementations of independently-developed components. To address these differences without changing the components, intermediary software components, called mediators [START_REF] Wiederhold | Mediators in the architecture of future information systems[END_REF], systematically compensate for the differences in the implementations of these components.

We propose an initial realisation of collaborative security whereby the security controls are identified using adaptive security techniques and their deployment is performed by first selecting the appropriate components, according to their capabilities, and then synthesising the mediators that enable them to interact successfully. The selection and mediation of multiple components as a means to enact security controls, rather than achieving integration or interoperability only, raises a number of challenges for collaborative security research.

The paper is structured as follows. Section 2 presents our framework for collaborative security that combines adaptive security, collaborative adaptation and an explicit representation of the capabilities of the software components. Section 3 describes the key techniques used in adaptive security to select, analyse, and deploy security controls. Section 4 examines the principal techniques used in collaborative adaptation to select and mediate components in order to satisfy some functional requirements. Section 5 introduces an implementation of collaborative security by combining and unifying techniques from adaptive security and collaborative adaptation. It also illustrates its application through a robotics example. Section 6 discusses the open research questions.

A FRAMEWORK FOR COLLABORATIVE SECURITY

Collaborative security aims to exploit the collaboration of multiple, heterogeneous, software-intensive components in order to meet security requirements in the face of changes in the environment, changes in assets under protection and their values, and the discovery of new threats and vulnerabilities. A framework for collaborative security bridges the gap between the security requirements and the components available in the environment. Our framework revolves around three concepts: security controls, capabilities, and mediators.

Security controls specify the mechanisms that need to be deployed in order to enforce security requirements. According to the value of the assets to protect, the potential threats, and knowledge of the system over time-the sort of attacks that have worked, their consequences, and how they were stopped-we must determine the appropriate security controls. The deployment of these security controls is achieved through the collaboration of multiple components with different capabilities.

Central in this framework is the notion of capabilities. The capability of a component models what a component can do, how it can do it, and under which conditions. In order to enable the analysis and reasoning necessary for meeting security requirements, we must be able to capture, represent, and reason about the capabilities of the components. Capturing capabilities allows us to express what are the components available in the environment. Representing capabilities allows us to describe the features of the components explicitly. Reasoning about capabilities allows us to select the components that need to collaborate in order to realise the appropriate security controls. As the selected components can be developed independently, mediators are used to enable them to interoperate.

Mediators enable heterogeneous components to interoperate by reconciling the differences in their implementations. As the components that need to interact are not known a priori, we must dynamically synthesise and deploy the appropriate mediators to enable the selected components to collaborate in order to realise the security controls. In subsequent sections, we elaborate on the opportunities and challenges provided by adaptive security and collaborative adaptation to support each of these elements. Specifically, adaptive security is concerned with the analysis of security requirements and the operational context in order to determine the security controls that must be deployed to keep a system secure. Collaborative adaptation is concerned with the selection of multiple components, according to their capabilities, and their mediation, in order to realise adaptations that cannot be handled using a single component, or multiple components in isolation.

Collaborative Security Framework

ADAPTIVE SECURITY

Adaptive security aims to enable systems to vary their protection in the face of changes in their operational environment. An adaptive security solution specifies how to: (i) monitor the environment and evaluate the properties of the operational context, (ii) determine the adequate security controls enabling the satisfaction of security requirements according to the properties of the environment, and (iii) deploy these security controls. Figure 2 illustrates the principal elements of an adaptive security solution, which are described in the following. Monitoring the environment. The system must be aware of the properties of its operational environment in order to adapt its protection accordingly. Monitoring provides the mechanisms that collect, aggregate, filter and report details collected from the environment [START_REF] Computing | An architectural blueprint for autonomic computing[END_REF]. In a security context, the focus of monitoring is on the assets and their values as well as on potential threats and vulnerabilities. Besides techniques that detect violations of the security requirements [START_REF] Lazarevic | Intrusion detection: A survey[END_REF], it is also possible to detect threats by calculating the likelihood of a potential violation of security requirements based on the correlation between past events [START_REF] Lorenzoli | Detection of security and dependability threats: A belief based reasoning approach[END_REF].

Security Requirements

System

Secure Operational Environment

Adaptive Security

Security Controls Determine

Determination of security controls.

Deciding what security controls are adequate is difficult because security threats are diverse and often unpredictable, and because the security controls selected often impact usability, performance, and other quality attributes of a system. Hence, the determination of security controls is a multi-objective and costsensitive decision-making problem [START_REF] Yuan | A systematic survey of self-protecting software systems[END_REF]. A requirement-driven approach for adaptive security enables analysing and reasoning about the costs and benefits of the security controls. For example, Salehie et al. [START_REF] Salehie | Requirements-driven adaptive security: Protecting variable assets at runtime[END_REF] propose an approach in which a runtime model that combines goals, threats, and assets models is used to evaluate the cost and benefit of applying each security control and choosing the most appropriate one.

Deployment of security controls. As most modern software systems are distributed and increasingly connected, the deployment of a security control may necessitate intervention at different parts of the system. DISCOA [START_REF] Demir | Discoa: architectural adaptations for security and qos[END_REF] defines a model-driven approach to support the deployment of security controls using point cuts over the architectural model of a specific system. Design-time security patterns are increasingly used to provide flexible and effective solutions for incorporating security mechanisms into software systems [START_REF] Fernandez-Buglioni | Security patterns in practice: designing secure architectures using software patterns[END_REF]. However, security controls need not be enacted using a single component but rather through the collaboration of multiple components available in the environment. In the following section, we therefore describe techniques to make components collaborate, albeit to satisfy functional requirements.

COLLABORATIVE ADAPTATION

Collaborative adaptation aims to address complex adaptations that cannot be handled by a single component, or by multiple components in isolation. A collaborative adaptation solution specifies how to: (i) represent capabilities in order to provide an explicit description of the components and enable reasoning about their collaboration, (ii) capture the capabilities of the components available in the environment, and (iii) synthesise and deploy the appropriate mediators that enable the selected components to interoperate even though they have heterogenous implementations. Figure 3 illustrates the principal elements of a collaborative adaptation solution. Representing and reasoning about capabilities. Since a capability models a component, its representation depends on the kind of analysis and reasoning that need to be performed on the associated component.

Tropos [START_REF] Bresciani | Tropos: An agent-oriented software development methodology[END_REF] defines a capability as "the ability of an actor of defining, choosing and executing a plan for the fulfilment of a goal, given certain world conditions and in presence of a specific event". In this definition, capabilities are used in the context of an agent-oriented software development methodology rather than in a runtime environment. We regard the capability of a component as independent of the plan it has to execute, and which may change at runtime.

In the Semantic Web Services domain [START_REF] Martin | Bringing semantics to web services with OWL-S[END_REF], a capability describes what the service does, i.e. the functionality it provides to its clients. It is described using the inputs, outputs, pre-, and post-conditions of the service, all of which are associated with concepts in some domain ontology. In addition, a process model specifies how the service achieves its capability and a service grounding describes the information necessary to invoke the service.

An ontology-based description of services has many advantages: (i) it promotes the semantic matching between clients requests and available services, (ii) it eases the construction of composition of services by making explicit the input, output, pre-and post-conditions of the services as well as their behaviours, and (iii) it facilitates interoperability by formalising both the meaning of the input/output and the behaviour of services.

Nevertheless, solutions based on process algebra and automata have proven more suitable for modelling and analysing the behaviour of components. Hence, they are often used to specify, formally, the behaviour of components (and connectors) in a software architecture.

Capturing capabilities. In ubiquitous computing environments, components often advertise their presence using standard discovery protocols (e.g., UPnP-SSDP, Bonjour, and Jini) [START_REF] Tanenbaum | Distributed systems: principles and paradigms[END_REF]. However, these discovery protocols often only provide the syntactic interfaces rather then a rich capability representation. Consequently, learning techniques are often used to infer additional information about the components and complete their capabilities. The additional information can include the semantics of the interface of a component [START_REF] Bennaceur | Machine learning for emergent middleware[END_REF], its behaviour [START_REF] Lorenzoli | Automatic generation of software behavioral models[END_REF], or its non-functional properties [START_REF] Ghezzi | Managing non-functional uncertainty via model-driven adaptivity[END_REF].

Synthesis of mediators. Mediators enable heterogeneous

components to interoperate in a non-intrusive way, i.e. without changing the internal implementation of these components. Mediation research has thus far focused primarily on design time activities [START_REF] Issarny | Composing distributed systems: Overcoming the interoperability challenge[END_REF]. There is however a shift towards runtime synthesis of mediators. Furthermore, the complexity of software systems is such that it is difficult to develop 'correct' mediators manually; i.e. mediators that guarantee that the components interact without errors (e.g., deadlocks) and terminate successfully. Inverardi and Tivoli [START_REF] Inverardi | Automatic synthesis of modular connectors via composition of protocol mediation patterns[END_REF] propose an approach to compute a mediator that composes a set of pre-defined patterns in order to guarantee that the interaction of components is deadlock-free. Cavallaro et al. [START_REF] Cavallaro | Satisfying requirements for pervasive service compositions[END_REF] combine assembly methods with pairwise mediators to enable the satisfaction of functional requirements. The former consider the structural constraints and specify a coarsegrained composition of components based on the functionality provided or required by each component, while the latter enforce this composition despite the behavioural differences that may exist between each pair of components given the correspondence between the interfaces of the components.

However, in environments where there is little or no knowledge about the components that are going to meet and interact, the complete generation of suitable mediators must happen at runtime while existing approaches assume to be given the correspondence between the interfaces of components or that some mediation patterns are known a priori and composed at runtime. In addition, the synthesised mediators solve the differences between components only at the application-level while in a world increasingly populated with mobile and ubiquitous computing technology, the differences between components span both the application and middleware layers.

Deployment of mediators.

As a conceptual paradigm that facilitates the communication and coordination of distributed components despite the differences in hardware and operating systems, middleware has often been used as an enabler for collaborative adaptation. For example, M 2 [START_REF] Yang | Enabling collaborative adaptation across legacy components[END_REF] introduces a message-based collaboration protocol to implement collaborative adaptation and defines an interface to plug legacy components. Nevertheless, when collaboration takes place at runtime, it is necessary to execute mediators that are automatically synthesised for that purpose. Starlink [START_REF] Bromberg | Bridging the interoperability gap: Overcoming combined application and middleware heterogeneity[END_REF] is a runtime framework that executes mediators specified using a domain-specific language that describes the behaviour of this mediator and the data translations that it must perform. Starlink also hides the heterogeneity of middleware protocols by generating, at runtime, the appropriate parsers and composers that translate network messages into and from the actions of the domain-specific language.

However, collaborative adaptation targets integration and interoperability and is agnostic to security concerns. In other words, collaborative adaptation solutions cannot readily be used to satisfy security requirements as they do not explicitly reason about assets and their values as well as potential threats and vulnerabilities of the system.

TOWARDS COLLABORATIVE SECURITY

We propose an initial solution for collaborative security, called collaborative adaptive security, based on our work on requirement-driven adaptive security, which is supported by the SecuriTAS tool [START_REF] Pasquale | SecuriTAS: a tool for engineering adaptive security[END_REF], and dynamic synthesis of mediators in ubiquitous environments, which is supported by the MICS tool [START_REF] Bennaceur | Dynamic Synthesis of Mediators in Ubiquitous Environments[END_REF]. Collaborative adaptive security enables the selection and mediation of components to deploy the adequate security controls in order to keep the system secure in a changing operational context. Figure 4 To determine the adequate security controls, SecuriTAS maintains a runtime model that combines goal, asset, and threat models, and uses it to compute the utility of each security control. The security goals are associated with pre-defined security controls. Assets are linked to the security goals and associated threats. Once the security controls are identified, we consider the capabilities of the available components and make them collaborate to realise these security controls.

The capabilities of components are represented using a combination of ontologies and transition systems. Ontologies are used to describe the high-level functionality the component requires from or provides to its environment, and to define the semantics of the actions of its interface. Transition systems are used to specify the behaviour of the component formally.

To determine which components need to collaborate to enact the selected security control, we must match the goal model against the high-level functionalities of the available components. For the moment, let us consider that the leaves of the goal model correspond to the high-level functionalities of the available components. However, the collaboration between independently-developed components is often hampered by differences in their interfaces and behaviours. Therefore, mediators are synthesised which systematically compensate for these differences by mapping the interfaces of the components and coordinating their behaviours.

The automated synthesis of mediators, implemented by MICS, is performed in several steps. The first step is interface matching, which identifies the semantic correspondence between the actions required by one component and those provided by the others. We incorporate the use of ontology reasoning within constraint solvers, by defining an encoding of the ontology relations using arithmetic operators supported by widespread solvers, and use it to perform interface matching efficiently. For each identified correspondence, we generate an associated matching process that performs the necessary translations between the actions of the components' interfaces. The second step is the synthesis of correct-by-construction mediators. To do so, we analyse the behaviours of so as to generate the mediator that combines the matching processes in a way that guarantees that the components progress and reach their final states without errors. The synthesised mediator is the most general component that ensures freedom of both communication mismatches and deadlock in the composition of the components [START_REF] Bennaceur | Automated mediator synthesis: Combining behavioural and ontological reasoning[END_REF]. The last step consists in making the synthesised mediator concrete by incorporating all the details about the interaction of components. To do so, we compute the translation functions necessary to reconcile the differences in the syntax of the input/output data used by the components and coordinate the different interaction patterns that can be used by middleware solutions. Hence, mediation is tackled from the application to the middleware layer in an integrated way. The mediators we synthesise act as: (i) translators by ensuring the meaningful exchange of information between components, (ii) controllers by coordinating the behaviours of the components to ensure the absence of errors in their interaction, and (iii) middleware by enabling the interaction of components across the network so that each component receives the data it expects at the right moment and in the right format.

We have been experimenting with collaborative adaptive security an early prototype demonstrator using two robots: a programmable autonomous vacuum cleaner (iRobot Cre-ate1 ) and a humanoid robot (NAO2 ). The two robots need to collaborate in order to secure a particular area in our laboratory. The iRobot Create has a simple capability that consists of executing the moving commands it receives. NAO has the object-recognition capability and can indicate to iRobot Create the area in which it can move. Both iRobot Create and NAO rely on discovery protocols to advertise their presence in the environment, the former uses Bluetooth discovery while the latter uses Bonjour. Nevertheless, putting iRobot Create and NAO in the same environment is not enough to satisfy the security requirements, as they cannot interact with one another spontaneously. What is needed is a mediator that makes them collaborate in order to realise the security requirement. Therefore, a mediator is synthesised which exchanges messages with both robots through their specific interfaces, using the iRobot Create Open Interface to communicate with iRobot Create, and NAOqi to communicate with NAO; and coordinates the behaviours of the components by first receiving the messages from NAO then sending the commands to iRobot Create.

Analysis. To present collaborative security more precisely, we describe it using Jackson and Zave's framework for requirements engineering [START_REF] Jackson | Deriving specifications from requirements: An example[END_REF]. Let E denote environment properties, Rs denote security requirements, and S denote the specification of a software system that satisfies the security requirement Rs, i.e. S, E ⊢ Rs. When the environment properties evolve into E ′ , the specification of the software system S, and the software system itself, may no longer satisfy the security requirement Rs, i.e. S, E ′ ⊢ Rs. As a result, the system must be adapted so as to keep the security requirements satisfied.

To ensure that the security requirement Rs remains satisfied in the environment E ′ , adaptive security transforms the specification of the software system S into a specification S ′ such that S ′ , E ′ ⊢ Rs. S ′ is obtained from S through the deployment of the adequate security controls. Nevertheless, the specification S ′ need not be achieved using a single software component; rather, we may take advantage of the capabilities of the different components available in the environment and make them collaborate so as to realise S ′ .

Let C = {C1, . . . , Cn} denote the set of the capabilities of the components available in the environment E ′ . Note that C may include the component(s) of S as well. None of the components available in the environment is able to satisfy the security requirement Rs, i.e. ∀Ci ∈ C : Ci, E ′ ⊢ Rs. It might be the case that even the conjunction of multiple components cannot satisfy the security requirement Rs, i.e. ∀C i ⊆ C : C i , E ′ ⊢ Rs. Collaborative security seeks a subset of components C j , together with the specification M of the associated mediator(s) such that C j , M, E ′ ⊢ R.

A RESEARCH AGENDA

The increasing ubiquity of connected devices both challenges and supports security. The challenges arise from the frequent and unpredictable changes in the environment, in assets under protection and their values, and the discovery of new threats and vulnerabilities. The support comes from the plethora of devices that can be composed in a multitude of ways in order to protect valuable assets. Collaborative security aims to address new or changing threats by enabling the runtime deployment of adequate security controls through the collaboration of the components available in the operational environment. In this paper, we suggested that collaborative security may be realised by combining techniques from adaptive security and collaborative adaptation. Nevertheless, many challenges remain.

The choice of security controls need not be specified but may be elicited according to the capabilities available in the environment. We envision inferring, at runtime, new security controls that a developer or a user did not consider at design time. We are also considering the use of security arguments to drive the satisfaction of security requirements [START_REF] Haley | Security requirements engineering: A framework for representation and analysis[END_REF]. We are thus investigating if argumentation can be used to determine the necessary security controls. Attempting to construct a security satisfaction argument exposes trust assumptions and oversights within the system that can affect security. At runtime, we can evaluate these assumptions to decide if they might be relaxed or invalidated. In addition, as ubiquitous computing and cyber-physical systems can influence their environment, they might change it in order to validate the necessary assumptions that would satisfy the security requirements. In addition, the trustworthiness of the individual components may help determine the components that need to collaborate in order to achieve security.

Finally, while collaboration can help maintain security requirements, how can we prevent it from introducing vulnerabilities? In other words, how do we synthesise mediators that constrain the collaborative behaviour so as to disable anti-goals and prevent attacks from succeeding?

We believe that collaborative security is a fertile research area, with both potential and challenges, and we invite other researchers to collaborate with us in addressing some of these challenges.

Figure 1 :

 1 Figure 1: Collaborative Security Framework Figure 1 depicts the main elements of the collaborative security framework and the functions associated with each of them. In subsequent sections, we elaborate on the opportunities and challenges provided by adaptive security and collaborative adaptation to support each of these elements. Specifically, adaptive security is concerned with the analysis of security requirements and the operational context in

Figure 2 :

 2 Figure 2: Adaptive Security

  Figure 3: Collaborative Adaptation

Figure 4 :

 4 Figure 4: Collaborative Adaptive Security

  illustrates this solution.

			Security Requirements
	Determine	Security Controls
		Represent
		Capabilities	Reason	Synthesise	Mediators
		Capture
	Monitor
		Component 1	Component 2
			Component 5
	Component 3		Component 4
		Secure Operational Environment

Deploy

Collaborative Adaptive Security

http://www.irobot.com/us/learn/Educators/Create.aspx

http://www.aldebaran-robotics.com/en/

ACKNOWLEDGMENTS

We acknowledge SFI grant 10/CE/I1855 and ERC Advanced Grant no. 291652 (ASAP).