Let an economic space be characterized by the existence of a given distribution of locations, i.e. consumers' residential locations and producers' plants. It is equipped with a system of prices. The econo my is fuzzy because the economic behaviors of agents are imprecise.

In this context, spatial partial equilibria theories are applications of a fuzzy economic calculation model. The aim of the present paper is to study the conditions which must be fulfilled in order that the compatibility of consumers' equilibria and producers' equilibria be verified.

Mathematical tools are Butnariu's theorems which extend the Brouwer's and Kakutani's theorems to the cases of fuzzy functions and fuzzy point-to-set mappings.

Economic results are the extension of the Walras Law to a fuzzy eco nomic space and the formulation of a theorem which states the condi tions for the existence of a spatial general equilibrium in a fuzzy economy. This theorem is a generalization of a classical Debreu's re sult.

Keywords : Economic Space, General Equilibrium, Fuzzy Sets, Mathema tical Economics.

1. Introduction.

1.1. A fuzzy economy is such that : (1) economic spaces where men live (regions, market areas, urban influence zones, etc.) are imprecise ; they possess "more or less" constituent characteristics and they are not parti tioned into very homogeneous and well delineated sub-spaces ; (2) economic agents pursue vague and sometimes incompatible objectives ; the cons traints which limit their means are elastic, either because they are im perfectly appraised, or because they are objectively fuzzy.

The matter of the fuzzy economic spaces analysis is to state a forma lized theory which retains in full the nuances and gradations of the real world and the lights and shades of the spatial human behaviors (Ponsard, 1980[START_REF] Ponsard | History of Spatial Economic Theory[END_REF].

1.2. With respect to spatial behaviors, they must be analysed as fuzzy economic calculations, i.e. as optimization programmings of fuzzy objective-functions with elastic constraints. Then, consumers and producers spatial partial equilibria theory is a particular specification of the fuzzy economic calculation general model. Consumers optimal decisions are their demands and producers optimal decisions are their supplies.

1.3. The aim of this paper is to study the compatibility of fuzzy spatial partial equilibria, i.e. to state a theory of spatial general equilibrium in a fuzzy economy. More precisely, this paper is limited to the analysis of the existence conditions of such an equilibrium.

The first part is devoted to the description of the analysis frame work ; the matter of the second part is to state a theorem of equilibrium existence.

1.4. Remark : In order to avoid any ambiguity in the notation of mathe matical symbols, ordinary concepts (non fuzzy) are underlined, whereas fuzzy concepts are not. For instance, A c £ is read : A is a fuzzy subset of the ordinary reference set E_. This convention is only applied to sets and not to their elements. No ambiguity is possible.

2. The a n a l y s i s f r a m e w o r k .

2.1. The characteristics of the economic space.

Let an economic space characterized by n goods i (i = 1, ..., n), m con sumers j (j = 1, ..., m) and r producers k (k = 1, ..., r). The set of agents is finite, but large enough in order that the economy has a struc ture of competition.

The locations of economic agents are given and their distribution is indifferent. We note without any ambiguity the consumers residences with the help of the same indexes j, one and only one individual residen ce corresponding to each consumer. Thus, different values of these indexes are allocated to distinct residences which are located in a given place or in several places. In the same manner, producers plants are noted with the help of indexes k.

Although the following model is inspired by the Debreu's theory (1959), the definition of an economic good which is chosen is not that of a merchandise in the meaning stated by this author. It is well known that such a merchandise is described as a product or a service which is characterized by various properties, especially the date to which it will be available and the place where it will be accessible. Then, the value of a merchandise in the future is equalized with the value of the same merchandise at present through a discount rate. In the same manner, the value of a distant merchandise is supposed to be equalized with the value of the same merchandise which is available in a given place through an exchange rate.

But, if it is possible to state the present value of a merchandise available in the future with the help of a discount rate, the same thing is not accurate to state the local value of a distant merchandise with the help of an exchange rate. Indeed, the actualisation calculation is based upon the axiom of the depreciation of the future which lays the foundation of the exchange rate. For lack of a similar axiom in spatial analysis, Debreu's exchange rate has no theoretical foundation. Thenceforth, this definition of a merchandise does not allow to explicit the impact of space in the economic equilibria. Therefore the usual definition of an economic good must be kept. We call "located goods" the nonspatial goods equipped with the coordinates of their supply or demand places in economic space.

Then, the economic space is characterized by a price system which allows to state the nominal value of physical products and services at a given instant. The delivered price of a ith good unit which is demanded by the consumer (located at the place j) to the k^h producer (located at the place k) is denoted by p. ... It is equal to the sum of the factory-

1 J K
price and the transportation price from k to j :

^ijk " pik + ^i'kj where p.. is the factory-price of the good i at place k and p.,, • the ik i k j transportation price of the good i from k to j, with i' which designates the transportation service of the good i.

A price-vector, denoted by p, p = [p. ..], describes a spatial price system. The set of prices is denoted by P_. Thus : p € P_.

We put the assumption that one price at least is not null. Subsequently, this condition will be necessary to verify a generalized Walras Law.

2.2. The description of the fuzzy economy.

2.2.1. Imprecise preferences, fuzzy utility, sets of located possible and efficient consumptions.

Let X . be the set of the located possible consumptions of the jth J \nmr consumer. The elements x. of X. are vectors of 1ft whose compoundings J v J x. . . state the quantities of the good i which are demanded or supplied by v J the jth consumer to the k ^ producer. They are non-negative or non-positive according as they are demanded or supplied respectively.

To simplify, we put : nmr = 1. The elements x. of X. are vectors of 1 R 1. J J The jth consumer has an imprecise preference-indifference system des cribed by a fuzzy total preorder (Ponsard, 1981 a). Under some conditions which assure the existence of a topological totally preordered space, a fuzzy continuous utility function, denoted by , is stated. It is such that : J

M x ex x , -----> ^u(xi} e [0' 1L J J J 'j J
Thus we define a fuzzy subset of X., denoted by U ., such that :

J J U. = {x., u u ; y X. G X-: % ( * • ) £ [0, 1]> J J j J J j J
which describes a fuzzy objective in the jth consumer' s economic calcula tion.

The jth consumer disposes of a given budget, represented by the real w . G 1R . For a set X..* a spatial price system p and a wealth w., the set J J J of budget is defined by : B. = {x. ; tf x. £ X. : p.x . < w } "J J J " "J J j where p.x. < w. designates the budget constraint. J J But, except for some particular cases, it is elastic, so that the located efficient consumptions set (for a given constraint JB.) is no more J reduced to the classical frontier of the consumption technical optima.

It is a fuzzy subset of X since each element x. belongs "more or less" J J to X.. Thus, we construct a mapping, denoted by y r , such that :

_j j U , : X ,________ » [0, 1] j J V X . e x . , X. , ________ » y . (x.) G [0, 1] J " J J '* C . j and y -( x .) = 1 if p . x . = w . cj J J J = 0 if p . x . > w . J J (x.) G ]0 ,1[ if p.x. < w. Cj J J j
The mapping y. is dependent on w .. It is monotonous and decreasing J J for increasing values ofw.: ( w ' . > w .)=> [ (w* . -p.x.) > (w -p.

x.)] J J J J J j J => M' p (x .) r (x .). v . l C. l J J
Thus, we define a fuzzy subset of L , denoted by C., such that :

J J C. = (x ., M r ; y x. 6 X. : y r (x.) G [0, 1]} J J Cj j -J Cj J
which describes a fuzzy constraint in the jth, consumer's economic calcula tion.

2.2.2. Producers fuzzy objectives, sets of possible and efficient pro ductions.

Let _Y^ be the set of the possible productions of the kth producer.

The elements y of Y. are vectors of n 1 whose compoundings y. state

K K 1 J K
the quantities of the good i which are supplied or demanded by the kth producer to the jth consumer. They are non-negative or non-positive according as they are supplied or demanded respectively.

Transportations are production activities just like all the others.

For a production y^ in ^ and a spatial price system p, the produ cer's profit, denoted by G^, is by definition :

£« = p-V
The objective of the kth producer is the maximization of the fuzzy utility associated with the profit (Ponsard, 1982 a).

We construct a mapping, denoted by , which is the profit fuzzy k utility mapping. It is such that : and y ^ = ^ inaction assumption k y c (y, ) 6 ]0, 1] in all the other cases, k k

We find again, as a particular case, the classical assumption if the profit utility is maximal (y^ (y^) = 1) for the maximum amount of profit.

Th the fuzzy objective of the kth producer. It is such that Thus, we define a fuzzy subset of , denoted by G , which describes K K

g k = { v v ; H y K : € t 0 , 1 1 1 , k k
Now, instead of partioning the set into two classes, for a given technological constraint, that of efficient productions and its complemental class in Y^, we admit that all the elements of are "more or less" efficient productions.

Thus we construct a membership function of the elements of Y^, denoted by y , such that : Hk with y (y ) = 0 in the assumption of the production of wastes

H i K k y (y. ) = 1 in the classical case of maximal efficiency H k K y (y.) G ]0, 1[ in all the other cases, k k
We define a fuzzy subset of Y^, denoted by H^, such that :

H k = V v ! yk e \ : v V € [0' 111 k n k
which describes a fuzzy constraint in the k ^ producer's economic calculation.

2.2.3. Allocation of wealths and incomes.

The initial allocation of the stocks of goods i is given. Let w^ be m the vector of the jth consumer resources and w = £ w . the initial wealth j=i J in the economy.

The distribution of profit between the consumers is defined by the parts, denoted A..., of the net revenues of firms which are perceived by the consumers. These coefficients are assumed to be non-negative and their sum equal to one for the r firms in the economy.

With these hypotheses, each consumer has three different origins for his incomes : incomes proceeding from its profit parts, from the sale of its initial dotations and from the sale of the services which are inclu ded in its consumption set.

We state the hypothesis that each agent can supply a quantity of each good in order to avoid discontinuity solutions :

w. G T R n and 3x.£X./x.<w.. J J "J J J 2.3. Definition of the spatial general equilibrium in a fuzzy economy. We have a membership function, denoted by y0 , such that :

* [0, 1] y x G E, x 1 ----------a y (x) = y (x) A y (x) ~ F C
with the following conditions : y (x) -1 iff x is good for F and C y (x) -0 iff x is bad for F or C

An optimal decision is such that :

sup y (x) = sup [y (x) A y (x)] .
x

E * x e E F c

This formulation sends for a very important remark in the framework of spatial partial equilibria theories : objective and constraint have the same part in the decision-making process. Indeed, their relationships are symmetric since two fuzzy subsets of the same reference set are concer ned and the operation n is commutative.

Formally, a fuzzy economic calculation has a structure which is si milar with the structure of a fuzzy mathematical programming. Tanaka, Okuda and Asai (1974) prove that the solution for the problem of finding the best possible decision is to settle an element x of E such that :

sup y (x) = sup y (x), with A c E and x G £ * x G A p A = {x ; x G E : y (x) > y_(x)} - - C r i.e.
A is a subset of E_ such that the value of the constraint membership function is at least equal to the value of the objective membership func tion .

A good understanding of this result compels to state the three fol lowing comments :

(2.3.1.1.) The conditions for the function sup y (x) to be continuous x G A f are little restrictives (Ponsard, 1981(Ponsard, b, 1982 a) a). Among them, we find on the one hand the condition that the (non fuzzy) sets of possible consump tion and production be compact, and on the other hand the condition that the fuzzy subsets which describe objectives be strictly convex.

Mathematically, it would be indifferent to lay the strict convexity condition on the constraint rather than on the objective, since they have the same part in the decision making. But for economic motives, it is accurate to lay it on the objective. Indeed, in the consumer and producer spatial equilibria theory, it guarantees the continuity property of the fuzzy utility functions. Moreover in the producer equilibrium theory, the assumption of increasing returns does not put a problem since the strict convexity condition is not laid on the technological constraint.

(2.3.1.2.) Generally the solution is not unique. Especially the analysis of the unicity conditions points out that the strong convexity condition must take the place of the strict convexity condition.

(2.3.1.3.) In the particular case where the objective is precise and the constraint alone is fuzzy, then the fuzzy economic calculation can be solved by a different and much simpler method (Ponsard, 1982 b).

Consumers spatial partial equilibria.

Consumers maximize their fuzzy utilities with their elastic constraints of budget and taking into account the equilibrium prices which are viewed as parameters.

The jth consumer chooses a consumption x^ in a non empty fuzzy subset X . of X . such that :

J ~J X . = U . n C . J J J
where X. describes the demand fuzzy subset of the jth consumer.

At the equilibrium, the consumption x^. is such that :

sup y Y (x ) = sup u (x ) x . E X . j J x.EA uj J J -J J J - with A = (x . ; x. E X. : u (x.) > u (x.)} - J J "J C • J U . j
As the continuity of the function sup y (x.) implies that U. x . G A ui J J J -J be strictly convex, a result is that, tf x . G _A, sup y (x.) is strictly J

x. G X. i J J "J J quasi-concave and X. is strictly convex. Therefore X_. must also be strictly J J convex.

In the goods supply space, the places where the several commodities are demanded and the respective quantities purchased are obtained since x = [x. ] where k is the index of supply places of the goods indexed J 1JK by i which are elements of the vector x . j m m Now let x = Z x . be the total consumption and X = Z X . be the total j = 1 J j = 1_J consumption set, to which a fuzzy subset X, X c X_, is associated. It is defined as follows.

The total consumption is such that :

Vx(x) A x . f sup y |x . G X . * J. J (x.)l j J J m Z j = 1 x . J
This expression is not a quotient. It means that the sum of individual consumptions (under the lines) is equipped with a membership function, denoted by y , (above the lines) such that :

Vix : X , _______ » tO»

We remark that sup yy (x.) is necessarily non null, V j G [1, m], x . G X . X j J J " J J since any consumer demands at least a consumption which is equal to the physiological minimum.

The fuzzy subset X of X is such that the membership function of x is equal to the minimum of the membership functions of the individual demands x . to X .. Thus we have : J J X = {x, y ; y x G X : y (x) = £ [ sup y (x.)]} * * xj x . G X . Xj J J J -J J 2.3.3. Producers spatial partial equilibria.

Producers maximize their fuzzy utilities of profit with their elastic technological constraints and taking into account the equilibrium prices which are viewed as parameters.

The kth producer chooses a production y^ in a non empty fuzzy subset

Y. of Y. such that : k -k V = Gk n \
where Y^ describes the supply fuzzy subset of the kth producer.

At the equilibrium, the production y^ is such that : with A = iyk ; yk e 4 :

As the continuity of the function sup y (y ) implies that G be y. G A k k ' k strictly convex, a result is that, W y. G A , sup y (y ) is strictly \ 6 4 Yk quasi-concave and Y^ is strictly convex. Therefore, _Y^ must also be strictly convex.

In the goods demand space, the places where the several products are supplied and the respective quantities sold are obtained since y^ = [ y ^^]

where j is the index of demand places of the goods indexed by i which are elements of the vector y. . k r r Now let y = Z y be the total production and _Y = Z Y. be the k=1 k=1 total production set, to which a fuzzy subset Y, Y c is associated.

It is defined as follows.

The total production is such that : In order to simplify the notation, the symbol e designates the excess demand and the excess demand fuzzy point-to-set mapping. No ambiguity is possible in the context.

At the equilibrium, we must verify that e < 0. We must search for the conditions which ought to be fulfilled by e(p) in order to p be such that e(p) ^ 0 exists.

C o n d i t i o n s o f s p a t i a l g

e n e r a l e q u i l i b r i u m in a f u z z y e c o n o m y .

that :

P I - + e(p) = x(p) -y(p) -w
Mathematical tools are stated by [START_REF] Butnariu | -Fixed Points for Fuzzy Mappings[END_REF] who expresses the existence conditions of fixed points for fuzzy mappings. The following statement is slightly different from his.

3.1. Fuzzy point-to-set mappings and fixed points.

3.1.1. Let X be a non empty set and J_ a lattice with at least two elements, X the set of all mappings from X_ in L_ is denoted by L-~.

X

A fuzzy subset A of X_ is an element of L-such that :

A = {x, y A ; V x G X : y (x) G L}
The set of all fuzzy subsets of X. is denoted by ^0 0 .

3.1.2. A fuzzy point-to-set mapping over a set X is a mapping, denoted by T, from X_ to £P 00 which associates an element of (X_) to any x of X :

r : X ,_____ > ^(X) M X G X., X I -------» r(x) = A
We have : r(x) = {y, y ; y G X_, y = f(x) : y (y) G L j x x Thus, x is a parameter. Giving a particular value to y, we can write :

My) = {y, yr ; y G X : yr (x, y) G L_)
where y^, is the membership function of the couple (x, y) to the fuzzy subset r (y). x 3.1.3. An element x* of _X is called fixed point of the fuzzy point-to-set mapping T iff its membership function to A is at least equal to the member ship function of any element y of X.» i.e. iff y *(x*) > y *(y), V y G _X.

X X

In other words, a fixed point of a fuzzy point-to-set mapping T over X_ is an element x* such that y^Cx*, x*) ^ y^Cx*, x), V x G X_.

This definition is a generalization of the usual one. Indeed, if £ = {0, 1}, we find again the definition of an ordinary point-to-set mapping : y G f(x ) y (y) = 1. Hence, if y (x*) > y # (y), then y (x*) = 1 x x x and x* G f(x*).

3.1.4. Let £ be a subset of X_. The fuzzy point-to-set mapping T is closed iff the membership function y^Cx, y) is upper-semi continuous over £.

3.1.5. The fuzzy point-to-set T is convex iff its membership function is quasi-concave.

3.1.6. If is a real topological vector space, locally convex and Hausdorff-separated, £ a non empty, convex and compact subset of X, and T a fuzzy point-to-set mapping over £, an usual point-to-set mapping,

•A. denoted by T, can be associated to V by : r (y) = {y ; y G C : r (y) = V r (z)}.

x -X c n X Z G £ 3.2. Fuzzy function and fixed point theorem.

Definitions.

(3.2.1.1.) A fuzzy point-to-set mapping V over £, £ c X_, is said to be a fuzzy function iff, tf x 6 C, T i 0. It is said to be a "very fuzzy" A X function iff is a mapping over £.

(3.2.1.2.) A fuzzy point-to-set mapping over £, denoted by T 1 , can be associated with a fuzzy function T, by : r ' ( ) = (r(x, y) if y G ?(x)

x t o else Thus P = f .

Hence it results immediately that T and T 1 have the same fixed points and T 1 is a "very fuzzy" function.

(3.2.1.3.) A fuzzy point-to-set mapping T over £, £ <= X_, is said to be F-continuous iff, \j x G £, and for any open set £ in X, we have :

M y ) cDnCi3V£ /(y) / 1 ^0 0 £ £ n £
where Vi y ) is the set of all neighbourhoods of y in X3

.2.2. Fixed point of a fuzzy function. [START_REF] Butnariu | -Fixed Points for Fuzzy Mappings[END_REF] generalizes the Brouwer theorem (1909Brouwer theorem ( -1910) ) to the case of a fuzzy function.

(3.2.2.1.) Brouwer theorem. Let be a real topological vector space, locally convex and Hausdorff-separated, £ be a non empty, convex and compact subset of TR n , f a continuous mapping from £ to £ such that, \) x G C, the set {f(x )} is non empty, convex and compact, then it exists a fixed point x* of f, i.e. 3 x* £ £ / x* = f(x*).

(3.2.2.2.) Butnariu theorem 1. Let £ be a non empty, convex and compact subset of 11? n . If T is a fuzzy function over £ and if T % is F-continuous, then T has a fixed point in £.

Proof. The conclusion of paragraph (3.2.1.2.) states that it suffices to prove that P has a fixed point in £. We have P i x ) c £ since 0 < P (f(x)) < t)(x) and y 4 f(x) imply that r (y) = 0 < D(y).

Since T ' is F-continuous, it exists a neighbourhood V £ /(x) such that f* (V) c _D. So y z £ JC, we have : r T( W ( z ) c D(z).

X X

Let w £ V^. Then :

o < r ( f ( w )) 4 sup r ( f ( w ) ) = r'(f(w ) ) s < d(z). w v £ V V - Since £(f(w)) £ {0, 1}, we have : ID (f(w)) = 1 for w £ V_. Thus f(w) £ D, M w £ _V, i.e. f(V_) c D.
Therefore, we have proved that, \l x £ £, with f(x) £ D, 3 V £ /(x) such that f(V) c £, and f is continuous. Besides, y x G £, T is compact. Indeed, let (x.), i £ I, a series X 1 in r whose limit point is x*. Then f (x.) > r (y)? M y G and y i £ I. We have a series of continuous functions, denoted by g, such that :

g : I « -------» £.

e | -------) g(e) = { p ' / p'.e < p.e}

In order to verify subsequently the conditions of the fixed points theorems, prices are made standard, i.e. they are such that £ p. = 1. i,j,k 1J Let £={p;p€IP: Z p . =1}be the set of standard prices.

1J

The set £ is a simplex.

Thus, a continuous function, denoted g , is associated with any function g. It is such that :

g : E_,------» £ e t -------> g(e) = { p 1 / p' .e < p.e} This transformation brings no loss of generality. The prices of goods in the balanced or excess supply markets are relatively brought down as for the prices of goods in the excess demand markets.

In the same manner, we denote by 'e the F-continuous fuzzy point-toset mapping, associated with the excess demand fuzzy point-to-set mapping e, which has P as domain and £ as co-domain. Moreover, the fuzzy point-to-set mapping cp is convex in £ since it is the cartesian product of two convex point-to-set mappings. 4.1. The theorem of spatial general equilibrium existence in a fuzzy economy is true whatever be the economic space configuration. Provided that the competitive structure of markets be kept, it is applicable so as to the cases of a space ä la Thünen (concentrated demand, scattered supply), a space ä la Hotelling (scattered demand, concentrated supply), or a space ä la Lösch (scattered demand and supply). At last, it covers, as a particular case, the model of a classical aspatial economy (demand and supply concentrated in a single point).

4.2. However, this result is possible only when space is characterized in a poor manner. It has been described with the help of a set of points which are separated by given distances and all the prices, including the transportation prices, are settled in competitive markets. A richer characterization of space would start notable difficulties. We find again the idea that space is not economically neutral and its integration in the general equilibrium theory put specific problems (Mougeot, 1978).

4.3. The conditions of spatial general equilibrium existence are less constraining in a fuzzy economy than in an ordinary economy. Indeed, the consideration of fuzzy economic calculations permits to state a more general theory and above all to solve some fastidious questions, espe cially the problem of the equilibrium production with increasing returns.

But, the equilibrium conditions are yet restrictive enough, so that a fuzzy economic space, as an usual space, is commonly in a disequilibrium state. On this subject, the theory brings again a conclusion similar to the result of some land-use models [START_REF] Huriot | La formation du paysage économique[END_REF]. However, the disequi librium positions in space can be analyzed only by referring to the equi librium states. For that reason the concern of the spatial general equi librium theory remains.

4.4. The present paper is incomplete. Several complementary researchs must be looked at. Especially, the stability and optimality properties of the spatial general equilibrium in a fuzzy economy will have to be studied. In the same way, the assumption of competition in markets will have to be replaced by that of an oligopolistic economy. The theory will have to be formalized in terms of fuzzy games and fuzzy core. At last, in the present analysis, the locations of the economic agents are given.

The difficult problem of the existence of a spatial general equilibrium in a fuzzy economy with endogeneous locations remains open.

  p e r i s t o b e p r e s e n t e d at t h e Seco n d Inte r n a t i o n a l C o n g r e s s o f Ar ts a n d S c i e nces, R e g i o n a l S c i e n c e Sessions, to b e he l d J u n e 3-16, 1984, a t t h e E r a s n u s U n i v e r s i t y , Rotterdam, The Netherlands.

  E O R Y OF S P A T I A L GENE R A L E Q U I L I B R I U M IN A F U Z Z Y EC O N O M Y C l a u d e PO N S A R D P r o f e s s o r a t t h e Un i v e r s i t y o f D i j o n D i r e c t o r o f t h e I n s t i t u t e o f E c o n o m i c M a t h e m a t i c s (National C e n t e r for S c i e ntific Research) 4, b o u l e v a r d G a b r i e l -21000 DIJQNI (France) A b s t r a c t .

  2.3.1. Fuzzy economic calculation. Let £, E. = {x}, be the set of a priori possible alternatives. A fuzzy decision, denoted by D, in £ is by definition the intersection of the fuzzy subset F, F c E_, describing the aimed objective (the set of the "more or less" attained objective values) and of the fuzzy subset C, C c E_, des cribing the constraint (the set of the "more or less" satisfied constraint values) : D = F n C

  that the sum of individual productions (under the lines) is equipped with a membership function, denoted by y , is necessarily non null, \J k 6 [ 1, r], Yk since a producer does not contribute to the total supply in the inaction assumption. The fuzzy subset Y of Y^ is such that the membership function of y is equal to the minimum of the membership functions of the individual supplies yk to V Thus we have : Y = {y> u ; ü y e X : u (y) = A [ sup y (y )]} Y Y yk y k G 4 Yk X 2.3.4. Excess demand fuzzy point-to-set mapping and markets equilibrium. With the previous definitions, the excess demand in a fuzzy economy, denoted by e, is equal to : e = x -y -w It is such that : As x 6 X_ and y € Y_, the excess demand x -y -w is an element of a set, denoted by £, with £ = X. -X. Then we define an excess demand fuzzy point-to-set mapping e such where x(p) is the value of the demand point-to-set mapping for a price p, y(p) the value of the supply point-to-set mapping for a price p and w the initial resources.

A

  Let y = f(x) be the unique element of £ belonging to T . If the X A function f : x,_____ >f(x) has a fixed point x* in £, then x* = f(x*) 6 r * and the theorem is true. Since £ is convex and compact in f c n , f has a fixed point in C if f is continuous by virtue of the Brouwer theorem. Then it suffices to prove the continuity of f to complete the statement. Let x £ £ and £ be an open set in tR," such that f(x) £ D.

□ 3 . 3 .

 33 Fuzzy point-to-set mapping and fixed point theorem.Butnariu generalizes theKakutani theorem (1941) to the case of a fuzzy point-to-set mapping.3.3.1. Kakutani theorem. Let il? n be a real topological vector space, locally convex and Hausdorff-separated and £ be a non empty, convex and compact subset of lf?n . Let £ be an upper-semicontinuous point-to-set mapping such that :(i) W x G £, £(x) is a non empty, convex and compact set (ii) the set graph (£) = (J ({x} x £(x)) is closed in If? n x ff?n , x G £ then it exists a fixed point x* of £ in £, i.e. 3 x* G £ / x* G £(x*).3.3.2. Butnariu theorem 2. Let _X be a real topological vector space, locally convex and Hausdorff-separated, and £ be a non empty, convex and compact subset of X_. If T is a closed and convex fuzzy point-to-set mapping over £, then T has a fixed point in £.Proof. The fuzzy point-to-set mapping T has a fixed point x* iff the ^ A point-to-set mapping T has a fixed point, i.e. iff x* G T(x*). Indeed x* is a fixed point of T iff y *(x*) > y *(y), which implies that x* G T(x*). F i 0. Indeed T is an upper-semicontinuous point-to-set x x mapping. It has a maximum y and effectively attains it in compact subset C of H? n . Thus 3yGC/yGr a is convex. Indeed, let (y, z) be element of C and r G L, . If y G T and z G T , then r (ry + (1 -r)z) > A (r (y),r (z)) the quasi-concavity of the membership function of the pointto-set mapping r. Moreover, r (ry + (1 -r)z) = sup r (w) by virtue of X

  From that, r (x*) = lim sup r (x.) r (y), \J y G C, by virtue of the x x i x -•V upper-semicontinuous property of r . Consequently, r is a closed subset ^ x x of the compact set £. So Tx is compact. At last, the set graph (J ({x}* T(x)) is closed. Indeed, let (x.) x G £ 1 and (y .), i 6 I, be two series in C such that (x., y.) be elements of the 11 --i' 7i set graph, U i G _£ Since £ is compact, lim(x^) € £. Moreover, rx (yi } » rx (y), y y g £, w i g j,. If x ^________*x* and y^ _______^ y* in X., therefore in £ since £ is compact, then :A r *(y*) = lim sup T (y.) >j lim sup T (y), tf y (upper-semicontinuous, we have : r ^(x*) >, r # (y), M y G £, i.e. (x*, y*) is an element of the graph and, by definition, the graph is closed. 3.4. Walras generalized Law. Let an excess demand fuzzy point-to-set mapping e which associates the subset e(p) of £ with any price vector p of £, such that : e(p) = x(p) -y(p) -w.

  Therefore, the assumptions of Butnariu theorem 2 are verified and the fuzzy point-to-set mapping cp has a fixed point in E_. By virtue of the Walras generalized Law, the fixed point corresponds to a competitive equilibrium state. Indeed, it exists a vector (p*, e*) ofPxE such that : (p*, e*) E cp(p*, e*) = (h (p * ), e(p*)) Then we have : [p* G h(p*) and e* G e(p*)] => p G P_ : p.e* ^ p*.e*

□ 4 .

 4 C o n c l u s i o n .

  respectively, are non empty, compact and strictly convex by virtue of the continuity conditions of the objective functions in the consumers and

	producers fuzzy economic calculations (see 2.3.1., 2.3.2. and 2.3.3.).
	Now let the fuzzy point-to-set mapping, denoted by cp, such that :
	cp ; P_ x	^ _P x £
	(p, e) |--------> cp(p, e) = {h(p), e(p)}
	This fuzzy point-to-set mapping is closed. Indeed, its graph :
	G={(x, y)G(PxE) cp --	/yGcp(x)=G xG} ' h e
	is closed because it is the product of two closed sets.

Acknowledgements

The author wishes to thank Mr. M. Prevot (I.M.E.) and the participants to a seminar held at the Catholic University of Louvain, Belgium (March 19, 1984), for fruitful discussions. Of course, he alone is res ponsible for any shortcomings in the text.

The following theorem states the conditions for which the groping process tends to a price equilibrium in all the markets.


where V denotes the maximum of the membership functions and A denotes the minimum of the membership functions.

Decision making under uncertainty requires not only measures of the uncertainty of situations that we try to recognize , but also an estimate of the imprecision from which they are determined.

Tnis imprecision can be the result either of a lack of exactness in the measure of the elements which are necessary to the determination of the states of nature or the purely subjective interpretation of these states.

Through a subjective measure of the non-measurable imprecision, the purpose of the fuzzy expected utility, which is investigated, is to translate with a great accuracy the imprecise behaviour of the decision-maker in an uncertain world. Consequently we propose to introduce first the probability of a fuzzy subset, or fuzzy event, to the theory of fuzzy utility, also called "fuzzy sto chastic utility".

On the other hand the uncertainty can correspond to an information state where a decision can lead to alternative results from which the probability may be unknown. Moreover most of the information of the decision-maker is often imprecise, incomplete and may be inaccessible on an exact number form. For these reasons, it is difficult for an individual to define a probability law of a fuzzy subset, so that we shall use later on a weaker structure than the one of probabi lities, where we no longer study what can happen but what could happen. The change form probabilities to possibilities allows the decision-maker to choose what he does prefer from what is possible. We will speak in this case of "fuzzy possibi-1istic utility". Using a set of well defined axioms (such as the existence of a fuzzy complete preordered structure on the set of actions ; the continuity of pre ferences ; the existence of a mixing operation on the set of actions...) it is possible first to determine a function of fuzzy expected utility. More exactly, according the information available, the decision-maker can assign a probability or a possibility to a given event, and define an additive fuzzy utility on actions.

We shall see later that tne choice* behaviour in uncertainty will thus be rationalized by a fuzzy expected function, which is continuous in the intrinsic topology.

-INTRODUCTION

In order to determine the axiomatic of a fuzzy decision problem in uncertainty, we will apply Bernoulli 's utility theory to a fuzzy case.

Let these be the following four elements :

< S, D, P(S k), U(Hj, S k) >

represents the set of states of nature also called world states. This set gives a full specification of the different stochastic factors of environment.

-= ( -1* -2 * * ' ' ' -k*"** -m]' ^ k subset of S is called an event.
^ c s.

The data belonging to have an empty intersection and their union is S .

P(S^ k) is the probability of k event. j) represents the set of all actions possible a priori.

D = j o p £ 2 ' -j .... -r]
An act is a mapping from the states of nature to the set of results

denoted: X =|x_ X_ ,,»•••» A n"j
u (Hi> S J is a fuzzy utility function. This represents the utility of

J ŝelecting

a fuzzy H. in an imprecise context, when S. event appears. Unlike the J -K usual case, the axiomatic of the fuzzy expected utility theory does not rest on a$>Borel' s field, but on a weak $ Borel' s field. Indeed, we will admit that for a given fuzzy decision problem, an economic agent can determine a weak if Borel' s field of events including all the information he has at his disposal.

Consider a referential denoted by ¿and a family of subsets denoted by <$ . fcfc L-; in general we represent I by a lattice or by an [0, 1] interval. cfis called a weak ¿f Borel1s field, if it verifies the following properties :

a) 0 e c f . h i f b) (Ac if , Be A r t B e $ c) , A^ »•••» A.j,...) U A | f 2 -THE PROBLEM

-FUZZY STOCHASTIC UTILITY

Consider j) = D^1 .We introduce the weak $ Borel's field.

=Îh1 , H2 ,..., H.,..., H i Hj C #.

We can associate a function d from S^ to _X with every fuzzy act d e H., J H. c j), such that

J d : s --^ d(s)
This function characterizes the decision of the individual, so that we can also write H. c jj = v J Confronted by a risky environment, the consequence of a fuzzy decision is the image on )( of P probability law by d mapping.

We obtain : d'^H.) e ¡5

V H. e

J J

The measure P* defined on (D,tf) structure by P*(H.) = P(d ^(H.)), is

J J
a probability law of a fuzzy decision on D.

P* is called image by d of P law.

P*(Hj) is the probability that the consequence of the fuzzy decision belongs to X. The comparison between decisions will finally amount to that between the associated P*, so we can eventually compare directly between them the probability laws on the structure of (j), ¡$ ). The fuzzy expected utility of a decision H . is J thus defined by the following formula : m V ( V = Ï U(Hj, Sk) . P(Sk) = P(Hj).

This equals the sum of fuzzy utilities to the conditional decisions H.,, J weighted by the probability of these events. It also corresponds to the probabi lity of a fuzzy subset H.. This latter is expressed by the fuzzy utility of a J fuzzy decision . M (d 1 > d3) > V ^dl 'd2^ A ^d2' d3 ^ dÎ n the imprecise context, the preference or indifference structure denoted by (H, Si) has the property of completeness. In classical theory this latter condi tion requires that the economic agent should always be able to compare two actions according to his preferences.

More precisely :

V dj, d^ e H2 , m ^ (d2) or

Nevertheless we have d^) = 0 if (d^, d£) = 0 (being a consequence of the fuzzy measure definition). This in fact,is the non comparability assumption. [START_REF] Ponsard | On the imprecision of consumer's spatial preferences[END_REF]. Unlike the usual theory which requires the complementary concept, this latter is not constraining.

Axiom 1 states that the choice behaviour of an individual can be rationa lized by a completefuzzy preorder denoted (j^, ^ ) in a fuzzy context.

A fuzzy utility U defined on a preference space (H, » is called fuzzy expected utility if the following definition holds. Definition 3.1 : For any fuzzy decision H^, and for any cue [0,i], the fuzzy expected utility is defined by :

U[<«. + (!-<*) A*h^(s)J = u( l*\\ (s)) + (1 -<*) u ( M H (S))
The second part of the above formula represents the fuzzy mathematical expectation of the fuzzy utility. So the definition of the fuzzy expected utility has a meaning only if the composition

(s ) + (1 -#) (s ) is introduced in the set H C D . 1 2
As in the usual theory, this composition is described by an imprecise lottery which admits H1 or H2 as a possible outcome with a and (1 -a) respec tive probabilities.

To obtain it we propose the following axiom :

AXIOM 2 :
e [ 0 ,l] H c H H x H -----> H dl' ^2~~---^ a dl + (1 " 01 ) d2" We have : 1) V dx, d2 e H2, a = 1 i d^ + (i -1) d2 = d j .
2) the property of Commutativity :

V d d2 e H2 , cte(o,l] « dj + (1 -«) d2 = (1 -a) d2 + « d3
) the property of distributivity :

V d j , d2 e H2 , V ^ e (0, i f

(}(a d^ + (1 -a) d2 ) + (1 -,3) d2 = 0 <x d^ + (I -$&)
A convex non-empty part of Rn is a mixture set if the general expression * d^ + (i -of) d2 is also convex. We say that we have the same result for a non empty set of probability measures which are all defined on a Borel' s field. For the economist M ' is both a mixture set and a fuzzy complete preordered set. I he mixture operation in this case becomes a "probabilized mixture operation".

We also note that property (3) aggrees with VON NEUMANN and MORGENSTERN's principle (1953) of composed probability.

Axiom 2 establishes all possible acts described from events included in ¥ weak Borel1s field. Moreover, the acts are generally conditioned by events. I hi s conditioning of acts allows us to define how the information is integrated in the decision-maker's choice. AXIOM 3 : Indépendance axiom.

V S_k e , & is a Borel ' s field.

V d ls d2 e H , 3

d 3 e H / d ^^U d ^ ^ di^/Sk = ) V d* 3 e H , d17^ U d ' ^ ^ d2/^ \J d ' Ŵhen
axiom III is verified in the preordered structure ( H , ^ ), we say that it is independent from ^ .

We can interpret this axiom in the following way :

"If two acts conditional to the same event are combined with a third act conditional to the complementary event, then the direction of preferences remains the same."

Ihe following lemma is an immediate consequence of the independence axiom.

Lemma The decision-maker prefers more or less an action d^ to another action ?■ " a t , < v di>-K l ( di ' dz ) is called the degree of strong preference for action d^ relative to action d^.

^g^(d2 ,d^) is called the degree of weak preference for act d^ relative to act d^.

The determination process of a fuzzy utility function is similar to the one explained by PONSARU (1979PONSARU ( -1984)), we will build however a fuzzy utility func tion, where the preference structure is imprecise in the choice of an act condi tional to an event.

The uncertainty can be found in the description of a fuzzy act.

3.3 -Existence and continuity of the fuzzy utility function.

Given the(Hy^ ) structure, the fuzzy utility is the numerical trans lation of the qualitative description of the conditional choice which is contained in the definition of imprecise preference structure.

We call fuzzy utility denoted U : any homomorphism from (H/c. ) to r n -/ -k i [ 0 ,1], > ) .

i.e. any application : u : H -----? [ 0 ,i] d1 : ------> u(dx) V (dpd^) e H2 » dl/sk ^d2/Sk <^==^ U^dI^ ^ U^d2Î f a fuzzy utility function exists for ) structure we also check that -k

V(dr d2) e H2, d: < d 2 4= ^u ( d 1) < u(d2) dl ^ d2 4--^ u(^i) = u (°*2 )
If U is a fuzzy utility on fuzzy conditional acts on a (Hy<-, ^ )

structure, it remains the same for the 0 composed function (in the^usual meaning), u = f 0 g ; where t is an increasing homomorphism for ([^0,1 J , ^ ) to({jJ,l^ )

Vdj, d2 e H2, dj < d ; /---^.u i d ^ -s u(d2) i^f [ g ( d 1) ] < f [g (Az )\
This function is defined on (H^<-, ^ ) up to an increasing monotonic transformation. Theorem 3.1 : If the imprecise structure (H/c. , is a complete preordered set, / j>k there exists a fuzzy utility function. Definition 3.2 : A fuzzy utility function is a real-valued function such that if :

U(dj) -u<dj/s1> + u(dj/s2> + ••• + U(dj/Sm ) = U • + U • + . . . + u. J 1 2 Jm m = 2 u k=l Jk m m Then d . ^C^d-. A .i u . ^ 2 u*. J ^ k=l Jt k=l 'k 4 = } U(dj) <U(d,)
From the above theorem and definition, we can deduce the following theorem :

Theorem 3.2 : If the imprecise preference or indifference structure ) is a complete preordered set, then there exists a fuzzy utility function -k additive on conditional acts.

AXIOM 4 : Allows us to prove the continuity of the fuzzy utility function.

V d ^ d^ e the fuzzy subsets :

H* = | V H / " H(d2) < ""(djlj H^ = ¿2 e _H / M h ^2^ > ^ H^dl^ are pseudo closed into H.
The topological space (_H,^ , ) is an imprecise preference structure ;

the preferences are continuous fortS if and only if Vd^e H* e € » e tS-Using Uzawa's theorem (1960) we can also prove that the (H/(-, 'g ) -k space is a complete preordered topological space. We can then define an additive fuzzy utility function on the conditional acts as being any continuous homomorphism from (H, ^ ^ ) i ----^ ( [ 0 ,1] , where ^a n d «4/* are the respective in trinsic topologies. Thus, given axioms 1 to 4, we can rationalize a choice beha viour in uncertainty by a fuzzy utility on (H/c , ). ~-k This fu^zy utility is continuous in its intrinsic topology, it is defined this way :

U(d) = 2 u(d/s ) k= 1 7-k
3.4 -Utility of fuzzy decision using fuzzy numbers.

We can further introduce a second type of imprecision in the fuzzy utility.

Indeed, to our imprecise preference structure we associate a fuzzy numerical trans lation of a qualitative description of the decision-maker's choice. In this way, tie utility of a fuzzy decision is no longer expressed by a precise number but by a fuzzy number. Therefore :

when H = (R J(s is the fuzzy numbers set.

The fuzzy utility of a fuzzy decision d./c; will be defined by :

The memberships functions of fuzzy numbers satisfy the properties of conti nuity, normalization, and quasi convexity.

However, in order that the fuzzy utility functions should retain the same characteristics, we show easily that the additivity of fuzzy numbers always possesses the same properties as those.

3.5 -Existence and continuity of a fuzzy stochastic utility.

The last two theorems allow us to define a choice behaviour in uncertain ty. This latter is rationalized by our axioms. At this level, we introduce the probability of an event S^, Sj,e lhis probaDility is considered as a behaviour coefficient, and it is defined on a 8b Borel1s field.

Theorem 3.3 : Existence of a fuzzy stochastic utility function.

Given a choice behaviour under uncertainty, when axioms 1 to 4 are satis fied, we show that, for an event c there exists a fuzzy expected utility which is continuous in its intrinsic topology such that :

This theorem is a consequence of the previous theorems, where we have demonstrated the existence and continuity of a fuzzy utility function which is additive on the conditional acts.

-FUZZY POSSIBILISTIC UTILITY.

A fuzzy decision problem in uncertainty is defined by using the possibility of an event S^.

Let the following four elements : < b, V 7T (bk), UiH., Sk) >

The axiomatic of the fuzzy possibilistic utility also rests on a weak Of Borel1s field.

As in the usual theory, the possibility is defined on a $ Borel's field. U(H., S ) is the fuzzy expected utility function.

J

The fuzzy possibilistic utility of fuzzy decision is :

V (H j> = n<V " < ["h-^ A ' (5k)J -k ■ s | < L u 'H J -^> A 'I <5k)] -V k L u (xjk) A M S , ) ] with Max * (S.,) = 1 S -k n (U.
) is the possibility of a fuzzy decision H.. Knowing the event, k this latter is expressed by a fuzzy utility. li (U. ) also corresponas to the possibility of fuzzy subsets.

JK

Consider again the axioms system : Aa IOM 1 : A fuzzy complete preorder exists on the set of actions H, H c D_.

H is the set of actions made possible for technical reasons. This result is proved with the SUGENO's theorem (1974) which is applied to fuzzy subsets :

If Fa = Vf £ f is continuous, Vf is a fuzzy measure of fuzzy subsets, then there exists «g ^ 0 such as / A f dv^s = v^| f > c •

-CONCLUSION

The fuzzy expected utility gives first a precise measure of the preferences of an individual by taking into account his satisfaction curve, and translate a set of decision rules.

However the introduction of fuzzy subsets weakens the rational critaria of decision, so that these latters are considered as reasonable and gives a good representation of the decision-maker's psychology.

More precisely the real behaviour of an individual is expressed by a more or less thick, convex or concave curve. This latter translates respectively the more or less strong preference or dislike for the risk. This thick curves express the imprecision which characterises individual behaviour, sensitive to the vague ness and the dispersion of utility values.

They gives a generalization of the usual theories. In particular, we find once more the single linear curve, which is representative of the indifference behaviour of the decision-maker.

On the other hand, the uncertainty is translated through the description of actions, thus the fuzzy stochastic and possibilistic subsets enlarge the view of uncertainty .

We note again that the axiomatic structure of possibility is weaker than the probability structure. Therefore the former can take into account unforesee able factors, and is well defined for the domain of uncertainty.

It is indeed more realistic and easier to evaluate what can happen than what must happen.

  fait 1 'objet d'une Communication au Vlth European Congress on Operations Research, Vienna, Austria, july, 19 -22, 1983, au XVème Colloque annuel de l'institut de Mathématiques Economiques, Dijon, le 25 novembre 1983.

3. 1 -

 1 System of Axioms for the fuzzy expected utility and Interpretation. The choice criterion of the decision-maker is explained by the preference concept relative to the various actions. We express this preference or indiffe rence by a binary relation denoted by St defined on D. Vd-^ e j), Vd,, e D we read, di ^d ^ by "d^ is preferred to d^", and d^d^ by "the action d^ is indifferent to the d2 action". Let H be the set of acts made possible for technical reasons. AXIOM 1 : A fuzzy complete preorder exists on the set of actions hi c 0 . The set has a fuzzy complete preordered structure if the fuzzy relation is reflexive and Max-Min Transitive. a) the relation Stis reflexive : V (d1, dj)e H 2, n ^(d p d j) = 1 b) the relation SI is A V transitive * : Vldj, d3 )e H2 .

  Given an act d, d e h, H C H , we call fuzzy conditional decision to event, c S , the restriction d denoted b y d ^ to event. -k Hy<. represents the decision set conditional to S^. k We have : V ( d x ,d2 ) e H2 , Sk c S di/sk U d2/Sk e M HI set is closed to a mixture of conditionnai act which is build from the event.

AXIOM 2 :

 2 The set jl c D is called fuzzy VA mixture operation t o w ards^ .Condition H c JD. We call fuzzy VA mixture operation (denoted M") towards the following convex arrangement. property of distributivity.X is a fuzzy subset.Its density of possibility isv : (R --->[0,lj and f(x) = Poss|x = xjConsider the F fuzzy subset of (R. We have :Poss | X = F j = Sup ^Min (F(x)), $ (x) j and Poss j X = ij = Sup </>(x).More precisely, this latter expression means that we have maximized on the fuzzy constraint F . Moreover for any A CfR, if ll Y (A) = Sup 'P(x) is the possibility measure of v .xThen, we can write :Poss | X = F ^ = /R Fdnx where J ^ Fd II = Sup [Min ( a, ' F > uj) JHence if < p is continuous, F is superlatively half continuous, strictly convexe ; and Sup F is compact.Then Poss j X = Fj = Poss X e A where VtfejjD.lj A = | x 6 |R : F(x) > u Q j.

  he decision-maker sets up a comparison between two fuzzy actions at a more or less strong level of preference or indifference. This level expresses the imprecision of his decision.

		Hence a fuzzy binary relation denoted	between the elements of ¡H2
	is defined by :
		dl ^ °2 = { ( dl 'd2)'	» V d l e il» V d2 e H, ^^( d 1 ,d2 ) e M J
	where / « ^( d ^^) denotes the level of preference and	indifference between the
	two actions and M is a complete preordered membership set. In other words, to
	each given preference or indifference system, a fuzzy subset denoted H is asso
	ciated.	o H is an element of the set of applications from H to M on the following
	pattern :
		--^ ^1 ,d2^ ' ,UH ' ^ ^1	^ d2 e	^ dI ,d2^ e
		6 S,	is a fuzzy complete preorderea structure.
			~k
	AXIOM 4 : Continuity axiom.
		Consider any three acts d ^ d2 , d3 e H , if	d2 ^* d3 , then tnere
	exists a number oc;0 <	1 such that ®cd^ + (1 -oc) d ^o j d	More
		specifically, we can say that a lottery ticket exists. This one asso
	ciates the two extreme acts respectively with the probabilities « and (1 -<*. )
	and it is equivalent to the intermediate act. These last two axioms are necessary

3.1.: If (_H,^ ) is a fuzzy complete preordered structure and if we have axiom 1 and Z then V S ^ to build a fuzzy utility function of a fuzzy decision, so that any available in formation is taken into account. 3.2 -Preference structure and uncertainty in a fuzzy context. 1 (,H6t) ts called an imprecisp individual preference or indifference struc ture. It is compounded by two structures denoted respectively (H, > )»(H.~ ) according to whether the relation §{, is a strict fuzzy preference relation or a fuzzy indifference relation. d2 if :

T (S^) is the possibility of event.

Axioms 3 and 4, respectively about absolute preference and continuity, are the same as those which are defined in the theory of fuzzy stochastic utili ty. The interpretation of these axioms are of course identical. The fuzzy possiwith Max tt(S. )= 1 S -k

Knowing events, we demonstrate the existence and continuity of such a fuzzy utility function of a fuzzy decision. This is done in the same way as the axiomatic of the fuzzy stochastic utility.

However the exitence and continuity proof of the fuzzy possibilistic utility is different.

Indeed, the mathematical expectation of the fuzzy utility corresponds with the possibility of a fuzzy event, also called possibility of a sensation by KAUFMANN (1977). This sensation represents the conditional utility of a fuzzy decision.

When S =fR, n{S^) is called density of possibility.

When ^ is finite, it(S^) is called possibility.

We write also the fuzzy possibilistic utility as :

We prove the existence and the continuity of such a function with the possibility subsets.

) is a fuzzy measure. So a fuzzy integral in SUGENO's meaning (1974) Jk exists.

IUU-) = J c U, dn

Jk -Jk

Let the U utility be a fuzzy variable denoted by X, we have then X : S ---^(R is a fuzzy variable.

bilistic utility expectation of H. fuzzy decision is : v J -ZAüEH l .

-ZADEH L.

-ZADEH L.

-ZADEH L.

-ZADEH L.


Matija Stevanovic

Kasper Revsbech

Jens Myrup Pedersen

Robin Sharp

Christian Damsgaard Jensen
email: christian.jensen@imm.dtu.dk

A Collaborative Approach to Botnet Protection

Keywords: Botnets, Botnet Detection, Collaborative Framework, Correlation Analysis

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

Introduction

During the last few decades, the Internet and applications based on it have experienced a tremendous expansion to the point at which they have become an integral part of our lives, supporting a wide range of services such as banking, commerce, healthcare, public administration and education. The growing reliance on the Internet introduces a number of security challenges that require sophisticated and innovative solutions. The main carrier of malicious activities on the Internet is malicious software, i.e., malware, which includes vira, trojans, worms, rootkits and spyware.

Botnets represent a state of the art deployment of malware that combines many existing advanced malware techniques. A bot is a computer which has been infected with some form of malware which can provide a remote attacker with total, unconditional and imperceptible control over the compromised computer. A botnet is a (usually) large collection of such compromised computers that are infected with the specific malware instance which enables them to be controlled by the malicious third party ("botmaster"). Botnets may range in size from a couple of hundred to millions of bots, spanning over home, corporate and educational networks covering different parts of the world. Botnets provide a collaborative and highly distributed platform for a wide range of malicious and illegal activities such as sending spam, launching distributed denial of service (DDOS) attacks, malware distribution, click fraud, distribution of illegal content, collection of confidential information and attacks on industrial control systems and other critical infrastructure. Some recent cybesecurity studies [START_REF]Botnets: Detection, measurement, disinfection and defence[END_REF][START_REF]Symantec global internet security threat report, trends for 2010[END_REF], claim that more than 40 percent of computers world-wide are infected with some kind of bot malware, thus being actively or passively involved in the malicious activities of a botnet. Additionally, these studies have shown that the average size of botnets is growing and that the biggest botnets can easily involve several million bots. The size of such botnets indicates the great potential in terms of processing power and available bandwidth. Pairing this with collaborative and coordinated action makes botnets rightfully regarded as one of the biggest threats to cybersecurity up to date.

Neutralisation of botnets involves technical, legal and political issues, and therefore requires an inter-disciplinary collaboration to achieve a successful result. At the same time, there is the challenge of raising computer users' awareness of the dangers posed by botnets as well as the challenge of persuading them to take the necessary steps to hinder the spread of botnets. Although complex in its nature, the problem of neutralisation and mitigation of botnets primarily relies on the ability to detect them. Extensive research efforts have therefore been made during the last decade to find ways to efficiently detect botnets. Many experimental systems have been reported in the literature, based on numerous technical principles and varying assumptions about bot behaviour and bot traffic patterns. However due to the dynamic nature of botnets and constant improvement of the malicious techniques, the success of the proposed detection and mitigation approaches has been limited. In this paper we present an overview of existing botnet detection techniques and we analyse their ability to cope with the challenges posed by modern botnets. We elaborate on the need for a more comprehensive detection approach in order to provide efficient and effective neutralisation of botnets. Finally, we introduce ContraBot, a collaborative botnet detection framework that combines approaches that analyse network traffic to identify patterns of botnet activity with approaches that analyse software to detect items which are capable of behaving maliciously.

The rest of this paper is organized in the following way: Section 2 examines the threat of botnets and identifies some trends in the development of botnets. A survey of earlier work on botnet detection is presented in Section 3. The need for a systematic approach to botnet protection is discussed in Section 4, which argues why combining existing approaches to botnet detection will provide better results in the fight against botnets. Section 5 presents the architecture of the ContraBot platform, which defines a collaborative framework for botnet detection and neutralization. Finally, a discussion of the ContraBot architecture and directions for future work are outlined in Section 6.

As a state of the art form of malware, bots are taking advantage of multiple malicious techniques and evolve at an unprecedented speed, presenting a considerable challenge to existing botnet defence systems. Current botnets are characterized by diversity of protocols and structures, usage of advanced code obfuscation techniques and a tendency to spread to new platforms.

The essential component, and at the same time the main carrier of botnet functionality, is the C&C (Command and Control) channel that is established between the botmaster and the infected computers. Moreover, the C&C channel represent the main characteristic that distinguish bots from the other malware forms. Botmasters rely on the C&C channel to issue commands to their bots and receive information from the compromised machines. C&C infrastructure has been evolving in recent years, so that today several control mechanisms in terms of protocols and structures are used for the realization of the C&C channel.

The earliest botnets utilized a centralized C&C network architecture, where all bots in a botnet contact one (or a few) C&C server(s) owned by the botmaster. The centralized C&C channels are usually based on the IRC or HTTP protocols. IRC-based botnets are realized by deploying IRC servers or by using an IRC server in a public IRC network. The botmaster specifies a channel, which bots connect to and listen on to receive commands from the botmaster. HTTP-based botnets are similar to the IRC-based ones. After infection, bots contact a web-based C&C server and notify the server with their system-identifying information via HTTP, while the server sends back commands via HTTP responses. IRC-and HTTP-based C&C have been widely used in botnets, but both of them are vulnerable to a single point of failure. That is, once the central IRC or HTTP servers are identified and disabled, the entire botnet will be disabled. Some examples of IRC and HTTP botnets that have been observed "in the wild" (Agobot, SDbot, Zeus, etc.) have had more than a million bots and have been successfully used for malicious actions such as DDoS attacks, identity theft, etc.

In order to be more resilient to counter-measures, the attackers have recently started to build botnets using decentralized C&C infrastructures such as P2P [START_REF] Grizzard | Peer-to-peer botnets; Overview and case study[END_REF] or advanced hybrid P2P structures [START_REF] Wang | An advanced hybrid peer-to-peer botnet[END_REF], where bots belonging to a P2P botnet form an overlay network in which any of the nodes (i.e. bots) can be used by the botmaster to distribute commands to the other peers or collect information from them. In these botnets, a botmaster can join, publish commands and leave at any time at any place. While more complex, and perhaps more costly to manage compared to centralized botnets, P2P botnets offer higher resiliency, since even if a significant portion of a P2P botnet is taken down (by law enforcement or network operators) the remaining bots may still be able to communicate with each other and with the botmaster to pursue their malicious purpose.

One of the first well-known examples of a P2P botnet was the Storm botnet [START_REF] Porras | A multi-perspective analysis of the Storm (peacomm) worm[END_REF] from 2008. Storm was estimated to run on over a million compromised computers and was primarily used for sending spam emails. It utilized Kademlia [START_REF] Grizzard | Peer-to-peer botnets; Overview and case study[END_REF], a decentralized Distributed-Hash-Table (DHT) protocol. Other noteworthy recent P2P botnets include Waledac [START_REF] Sinclair | The Waledac protocol: The how and why[END_REF] and Conficker [START_REF] Porras | Conficker C analysis[END_REF]. Although similar to the Storm botnet they employ self-defined communication protocols based on HTTP and fast-flux techniques. This illustrates the fact that modern botnets often use additional techniques for improving resilience and robustness of communication, such as obfuscation of existing communication protocols or development of new ones, encryption of communication etc. We can conclude that botnet detection approaches designed specifically to detect and mitigate centralized botnets will be less effective for such novel, highly decentralized botnets. Also, given the range of different C&C infrastructures that the botmaster can employ, a detection method targeting only specific C&C infrastructure cannot provide sufficiently effective detection of modern botnets.

Besides the diversity in structure and protocols, current botnets commonly employ code obfuscation techniques such as polymorphism and metamorphism. These enable the bot code to mutate without changing the functions or the semantics of its payload. Usually, in the same botnet, bot binaries are different from each other. Since signaturebased detection schemes look for specific data patterns within binaries, they require constant update of signatures in order to be able successfully detect bots. However even then these techniques are limited to detecting known bots.

Whereas almost all modern botnets have targeted personal computers (PCs), attackers are constantly searching for new ways of disseminating their product, such as finding new platforms to host botnets. One of the trends noticed at the beginning of 2012 was the occurrence of botnets on mobile telephones. The first mobile-based bot was Android.Counterclank, developed for the Android platform. This could be downloaded via the Android Market through several application packages. According to Symantec reports [29], this bot could carry out commands from a remote server and was capable both of stealing information from, and displaying ads on, infected Android handsets. Although promptly detected and taken down, this bot showed that botnets are slowly spreading to the smartphone domain. The popularity of smartphones and the fact they have a lot of processing power and bandwidth at their disposal will certainly continue to attract the attention of botmasters. The unique features of mobile devices such as communication via multiple technologies, like Bluetooth and NFC (Near Field Communication) in addition to the conventional IP network, could also provide mobile botnets with more stealthy and robust functioning. As existing detection techniques only cover PC-based botnets, further work is needed to counter the innovations seen in these novel botnets on smartphones and other potential new platforms.

Earlier Work on Botnet Detection

Botnet detection systems go back to the middle 2000s, and many experimental systems have been reported in the literature, with various aims in mind, and based on diverse technical principles and varying assumptions about bot behaviour and traffic patterns. Aims may include features such as automated operation, independence of communication topology and protocol, independence from payload content and real time detection.

Depending of the point of deployment, the detection approaches can be classified as client-based or network-based. In client-based approaches, the detection system is deployed within the client computer, and examines the computer's internal behaviour and/or traffic visible on the computers external network interfaces. Network-based detection, on the other hand, is deployed at the edge of the network (usually in routers or firewalls), providing botnet detection by passive monitoring of network traffic.

Like intrusion detection systems in general, botnet detection systems may be based on recognising characteristic patterns of code or data ("signatures") or patterns of behaviour. Likewise, they may be based on misuse detection -i.e. recognising signatures or behaviour patterns known to be associated with undesirable activities -or anomaly detection, where the idea is to detect noticeable deviations from normal behaviour. Misuse detection often gives fewer false positives, but plainly cannot be used to detect new bots or obfuscated variants of already known bots; anomaly detection is able to detect new forms of malicious activity, but may give many false positives if the pattern of normal activity changes. Thus there is a very wide range of potential combinations of approaches.

Client-based detection

Several client-based detection systems have been proposed. One of the earliest was BotSwat [START_REF] Stinson | Characterizing bots' remote control behavior[END_REF], which was based on a taint tracking system developed to discover programs that take advantage of received network data from an unreliable external source and to identify the potential remote control behaviour of bots. The main idea behind BotSwat is that a bot installed on the host computer has a specific pattern of behaviour that can be recognized by monitoring execution of an arbitrary executable binary, and tracing the traffic to its external source. This approach is directed at detection of individual bots by misuse detection and is independent of botnet topology and communication protocol.

The approach used by Masud et al. [START_REF] Masud | Flow-based identification of botnet traffic by mining multiple log file[END_REF] illustrates a method for botnet traffic detection based on the assumption that bots have a different response pattern from humans and that is possible to detect them by correlating multiple network flow log files on the hosts. The approach utilizes data mining techniques to extract relevant features from these log files and detect C&C traffic. The method offers several advantages such as real-time operation, and independence from communication protocol and topology. However, the approach has two major limitations. Firstly, it requires access to payload content, so it cannot detect botnets which use encrypted communication. Secondly, as the approach relies on the assumption that the response pattern of bots differs from that of humans, it is vulnerable to evasion techniques that include mimicking of human response patterns.

EFFORT [START_REF] Shin | EFFORT: Efficient and effective bot malware detection[END_REF] is one of the most recent client-based detection approaches, and is based on intrinsic characteristics of bots from both client and network aspects. The detection framework uses a multi-module approach that correlates bot-related information gathered by inspection of client computer internals, by monitoring the computer's interaction with the human user (key strokes and mouse input) and by monitoring traffic on the computer's external interfaces. The method has a number of advantages such as independence of topology and communication protocol, and the ability to detect encrypted and obfuscated protocols. The major limitation is that each detection module within the framework that detects specific bot-related occurrences can be evaded by suitably chosen evasion techniques. Nor can this technique provide real-time detection.

Network-based detection

Network-based detection is a more common principle used for detecting botnets and is primarily realised by passive network monitoring. Some of the earlier approaches of this type, such as Rishi [START_REF] Goebel | Rishi: Identifying bot-contaminated hosts by IRC nickname evaluation[END_REF], Snort [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF] and BotHunter [START_REF] Gu | BotHunter: Detecting malware infection through IDS-driven dialog correlation[END_REF] were based on misuse detection, using signatures of botnet malicious activity and C&C communication in order to detect them.

Rishi [START_REF] Goebel | Rishi: Identifying bot-contaminated hosts by IRC nickname evaluation[END_REF] was one of the first detection techniques to tackle the problem of IRC botnets. It uses a signature-based detection algorithm that matches the IRC nickname with typical nickname patterns of IRC bots. Rishi is based on passive traffic monitoring for suspicious IRC nicknames (Layer 7), IRC servers, and uncommon server ports (Layer 4). It uses a specially developed scoring system and n-gram analysis to detect bots that use uncommon communication channels that are commonly not detectable by classical intrusion detection systems. However this approach has not had much impact due to the fact that it does not have the ability to detect IRC botnets that use encrypted or obfuscated communication.

Snort [START_REF] Roesch | Snort -lightweight intrusion detection for networks[END_REF] is an open source network intrusion detection system (NIDS) based on misuse detection. Snort monitors network traffic, and is configured with a set of signatures and rules for logging traffic which is deemed suspicious. This method has several advantages, such as immediate detection and the impossibility of false positives, but of course can only detect known botnets. Moreover, as it performs deep packet inspection it can easily be defeated by encryption or obfuscation of payload content.

BotHunter [START_REF] Gu | BotHunter: Detecting malware infection through IDS-driven dialog correlation[END_REF] was the first open source botnet detection system available for broad public use. It was developed as an extension of Snort, by the addition of two anomaly detection plug-ins on top of Snorts existing signature database. BotHunter defines a model of the botnet infection dialogue process, which is intended to match the life-cycle of contemporary botnets, and uses it as a guideline to recognise infection processes within the network. However, this approach suffers from many shortcomings, primarily inherited from Snort, such as the inability to detect encrypted traffic, vulnerability to various evasion techniques and attacks directed at the content of the correlation matrix. Additionally BotHunter can only identify bots whose life-cycle follows the chosen model of infection.

Other network-based detection approaches are based on detection of statistical anomalies in network traffic, such as high network latency, high volume of traffic, traffic on unusual ports and unusual system behaviour, which are exhibited as a consequence of botnet communication. Important examples are BotSniffer [START_REF] Gu | BotSniffer: Detecting botnet command and control channels in network traffic[END_REF] and the approach of Karasaridis et al. [START_REF] Karasaridis | Wide-scale botnet detection and characterization[END_REF].

BotSniffer [START_REF] Gu | BotSniffer: Detecting botnet command and control channels in network traffic[END_REF] is a network-based anomaly detection approach developed to identify botnet C&C channels in a local area network without any prior knowledge of botnet signatures. It is based on the observation that, because of the pre-programmed activities related to C&C communication, bots within the same botnet will likely demonstrate spatial-temporal correlation and similar behaviour. The technique captures behavioural patterns of botnet traffic and utilizes statistical algorithms on them to detect botnets. BotSniffer was primarily developed to detect centralized IRC and HTTP based botnet C&C channels, and cannot cope with modern P2P botnets. Furthermore, the method is vulnerable to evasion techniques such as misusing whitelists, encryption, using very long or random response delays, injecting random noise packets, and evasion of the protocol matcher and etc. Karasaridis et al. [START_REF] Karasaridis | Wide-scale botnet detection and characterization[END_REF] used an anomaly-based botnet detection method aimed at detecting botnet controllers by monitoring transport layer data. The method was developed to detect IRC botnet controllers, i.e. IRC servers within large Tier-1 ISP networks. The approach is entirely passive and does not depend on botnet behaviour signatures or particular application layer information, so it is able to detect bots using encrypted and obfuscated protocols. However, the approach relies on an IDS to provide an indication of suspicious hosts, so it cannot detect unknown botnets or bots, and it cannot handle modern HTTP and P2P botnets.

In parallel with these efforts on network traffic in general, a subgroup of botnet detection approaches directed at detecting anomalies of DNS traffic emerged. DNS-based detection approaches rely on detection of patterns within DNS traffic that can indicate the presence of a bot or botmaster within the network. Some of the most prominent DNS-based approaches realize botnet detection by detecting anomalies of DNS traffic as in [START_REF] Villamarin-Salomon | Identifying botnets using anomaly detection techniques applied to DNS traffic[END_REF], performing DNSBL (DNS Black List) counter intelligence [START_REF] Ramachandran | Revealing botnet membership using DNSBL counter-intelligence[END_REF], capturing DNS group behaviour [START_REF] Choi | Identifying botnets by capturing group activities in DNS traffic[END_REF] or building a reputation system for DNS queries [START_REF] Antonakakis | Building a dynamic reputation system for DNS[END_REF]. Many novel classes of botnets (P2P, hybrid P2P), however, do not require a DNS service for their functioning so these approaches have a significantly limited detection scope. Some more recent approaches to botnet detection have attempted to detect patterns of botnet traffic by employing sophisticated machine learning techniques. Machine learning is used because it offers the possibility of automated, real-time recognition of patterns within traffic without a need for traffic exhibiting specific anomalies. Several detection approaches that employ machine learning have been proposed over the years such as in Strayer et al. [START_REF] Strayer | Botnet detection based on network behaviour[END_REF], Botminer [START_REF] Gu | Botminer: Clustering analysis of network traffic for protocol-and structure-independent botnet detection[END_REF], Lu et al. [START_REF] Lu | Clustering botnet communication traffic based on n-gram feature selection[END_REF], Saad et al. [START_REF] Saad | Detecting P2P botnets through network behavior analysis and machine learning[END_REF], and Zhang et al. [START_REF] Zhang | Detecting stealthy P2P botnets using statistical traffic fingerprints[END_REF], providing more or less efficient botnet detection.

Strayer et al. [START_REF] Strayer | Botnet detection based on network behaviour[END_REF] developed one of the first approaches that employed machine learning to detect patterns of botnet traffic within the network. Several machine learning approaches were utilized and their performance in classifying IRC traffic flows evaluated. The approach provides a real-time detection framework which has the ability to detect botnets even before a cyber-attack occurs. However, it only has the ability to detect IRC botnets with centralized topology and it requires external judgment, either by humans or machines, in order to generate reliable alarms for the existence of a botnet. This limits its practical usability.

BotMiner [START_REF] Gu | Botminer: Clustering analysis of network traffic for protocol-and structure-independent botnet detection[END_REF] uses an approach based on data mining, and was developed in order to successfully identify modern botnets, which can significantly differ in size, structure, communication technology and purpose. The technique assumes that bots within the same botnet will be characterized by similar malicious activity and similar C&C communication patterns. BotMiner employs clustering techniques in order to detect similarities within different hosts in the network. This technique is entirely independent of the C&C protocol, structure, infection model of botnets and it does not require prior knowledge of botnet specific signatures. However, by design it essentially targets groups of compromised machines within a monitored network, so it may not be effective at detecting individual compromised hosts. Moreover, the technique is exposed to various evasion techniques, and performs poorly in situations where stealthy P2P botnets, that mask their traffic within non-malicious P2P traffic, are present in the network.

A recent study in the field of botnet detection by Saad et al. [START_REF] Saad | Detecting P2P botnets through network behavior analysis and machine learning[END_REF] considers the problem of detecting P2P botnets by using machine learning techniques. The study evaluates the ability of commonly used machine-learning techniques to meet on-line botnet detection requirements such as adaptability, novelty detection and early detection. The study shows that machine learning algorithms have a great potential for detecting patterns of botnet traffic. However it also indicates that the performance of these techniques is highly dependent on the features selected for classification or cluster analysis and that they often have high computational requirements.

Zhang et al. [START_REF] Zhang | Detecting stealthy P2P botnets using statistical traffic fingerprints[END_REF] describe a novel botnet detection system that can identify stealthy P2P botnets, even when malicious activities may not be observable. Their approach focuses on identifying P2P bots within a monitored network by detecting their characteristic C&C communication patterns, regardless of how they perform malicious activities. To accomplish this, the system derives statistical fingerprints of the P2P communications generated by P2P hosts, and uses them to distinguish P2P bots from hosts that are part of legitimate P2P networks. This system can detect stealthy P2P botnets even when the underlying compromised hosts are running legitimate P2P applications (e.g. Skype). However, it targets only P2P bots, so it cannot cope with botnets based on IRC or HTTP. Moreover, as the method relies on numerous assumptions regarding P2P communication and P2P bot traffic patterns, it is vulnerable to evasion techniques such as using a legitimate P2P network, randomizing traffic patterns, using a malicious DNS server, or injecting P2P control messages.

Although each of the methods described above has a certain range of application, none of them can provide comprehensive botnet detection, fulfilling all of the detection requirements and providing a foundation for successful defence against modern botnets. Evidently the dynamic nature of bots and botnets requires an approach to botnet detection that would consider not just one characteristic of botnets but a variety of them, covering every aspect of the botnet life cycle. Some of the latest research efforts have therefore been directed at the development of novel combinations of detection approaches, which we look at in the next section.

Collaborative Botnet Detection

Faced with the many challenges of detecting modern botnets, researchers turned their efforts toward development of novel collaborative classes of detection approaches that integrate multiple principles of botnet detection. The main hypothesis behind these methods is that it is possible to provide higher efficiency and effectiveness of detection by correlating the findings of independent detection entities.

The general approach for correlating aspects of behaviour observed by various sensors is based on ideas presented by Strayer et al. [START_REF] Strayer | Botnet detection based on network behaviour[END_REF], Oliner et al. [START_REF] Oliner | Community epidemic detection using time-correlated anomalies[END_REF] and Flaglien et al. [START_REF] Flaglien | Identifying malware using cross-evidence correlation[END_REF], which extend older proposals made by Cuppens & Miège [START_REF] Cuppens | Alert correlation in a cooperative intrusion detection framework[END_REF] and Ning et al. [START_REF] Ning | Constructing attack scenarios through correlation of intrusion alerts[END_REF] for correlation of alerts in IDS systems. Using these or similar concepts, several authors have proposed botnet detection systems that correlate alerts from several detection enti-ties. Wang and Gong have proposed frameworks for collaborative [START_REF] Wang | Collaboration-based botnet detection architecture[END_REF] and fusion [START_REF] Wang | Botnet detection architecture based on heterogeneous multisensor information fusion[END_REF] detection while Zeng et al. [START_REF] Zeng | Detection of botnets using combined host-and network-level information[END_REF] proposed a combined botnet detection system.

To counteract the weaknesses of existing botnet detection architectures, Wang and Gong proposed several collaborative detection frameworks. The first framework [START_REF] Wang | Collaboration-based botnet detection architecture[END_REF] represents a hierarchical collaborative model that incorporates several independent detection systems, that use bot-related information from multiple sources such as network traffic, client computer internals and deployed honeypots. The second proposed framework [START_REF] Wang | Botnet detection architecture based on heterogeneous multisensor information fusion[END_REF] introduced the idea of combining multi-source information fusion with a collaborative detection framework. The framework envisions combining bot-related information originating from several sources (traffic monitors, IDSs, other botnet detection systems, firewalls) in order to determine the presence of a botnet within the monitored network. However the authors have not deployed or experimentally evaluated the proposed frameworks.

Zeng et al. proposed a hybrid detection approach [START_REF] Zeng | Detection of botnets using combined host-and network-level information[END_REF] that achieves botnet detection by combining host-and network-level information. The approach is based on the assumption that two sources of bot-related information will complement each other in making accurate detection decisions. Their system first identifies suspicious hosts by discovering similar behaviours among hosts using network-flow analysis, and then validates the identified suspects to be malicious or not by scrutinizing their in-host behaviour. The approach promises independence from the C&C protocol, topology and content of transmitted data. The main limitation is that it operates in time windows, which prevents it from providing real-time detection and makes it vulnerable to timebased evasions. Additionally the approach did not use the opportunity of including botrelated information originating from other sources, leaving space for further improvements.

The systems reported on by these research groups and others, although mainly proofs of concept, demonstrated that systems which combine information from multiple sources can achieve significantly increased accuracy in recognising malicious behaviour on a network wide scale. This sets a milestone for a new direction in the field of malware detection informally known as a collaborative detection.

The ContraBot Framework

The ContraBot framework represents a novel systematic approach to the detection and mitigation of botnets. Following the principles considered by the research groups presented in the previous section [START_REF] Strayer | Botnet detection based on network behaviour[END_REF][START_REF] Oliner | Community epidemic detection using time-correlated anomalies[END_REF][START_REF] Flaglien | Identifying malware using cross-evidence correlation[END_REF][START_REF] Wang | Collaboration-based botnet detection architecture[END_REF][START_REF] Wang | Botnet detection architecture based on heterogeneous multisensor information fusion[END_REF], ContraBot belongs to the emerging class of collaborative botnet detection approaches that integrate multiple principles of botnet detection, in order to provide more efficient and effective detection. The basic scientific hypothesis behind our method is that correlating the observations and analyses from client and network entities combined with in-depth analysis of harvested code will significantly improve the botnet classification ability, in comparison to todays state-of-the-art methods.

The ContraBot framework utilises several functional entities, as illustrated in Figure 1. A set of network sniffers placed within the network collect and pre-process network traffic data, while a set of activity monitors within the clients collect and pre-process information about client activity. The pre-processing is necessary in order to reduce the amount of data and also to allow selective analysis of particular traffic and/or client behaviour patterns. The output of this pre-processing is passed to a set of one or more Correlators, where it is analysed to reveal patterns of similar behaviour in different hosts and different parts of the network. Unusual patterns of activity, which may indicate an attack, will lead to the harvesting of portions of code from the hosts (and the associated network traffic), so that these can be further analysed by entities which investigate the code for malicious effects. In a similar way, Client distribution analysis entities analyse modules, apps and other forms of software fetched by the Clients from the network, so that well-known malicious software can be disabled or removed as in a traditional AV (anti-virus) system. The ContraBot framework will require input from a wide range of sources, including sensors installed by end users, ISPs and backbone network providers. The producers and consumers of this input often belong to different, possibly competing, organisations that employ different types of sensors, so it is important that all parties can evaluate the trustworthiness of the input they receive. The Correlation Framework will therefore include a trust management component that aims to establish the trustworthiness of input based on both direct experiences with the individual input provider and reputation ratings exchanged between the different Correlators in the Correlation Framework.

If the Correlators, distribution analysis entities or code analysis entities detect signs of malicious software, they pass this information to a sub-system which generates Warnings for distribution to Subscribers of the anti-botnet service. This allows the subscribers to initiate various counter measures, e.g. walled-gardens. In addition to warning messages, information (indicated by the dashed red arrows) is architecture of-passed back through the system, so that the analysis can be adjusted to focus more accurately on recognisable malicious activity. Both the network sniffers and client analysis entities have access to a (possibly distributed) storage system, to facilitate recording and subsequent in-depth analysis of detected threats.

Network Traffic Sniffing and Pre-analysis

The network sniffers that monitor and pre-analyse the traffic are entities operating in core networks, e.g. in an ISP backbone, and must therefore be capable of handling traffic at high data rates. For the realization of these sniffers FPGA (Field-programmable gate array) based network interface cards will be used. Such cards can guarantee high-speed packet capture with no packet loss, and they can also be configured to pre-filter/preprocess the packets according to some predefined parameters.

Detection of malicious traffic in core networks is not a new concept. Many approaches, ranging from signature based methods to more sophisticated methods based on machine learning, have been proposed and can be reused to a large extent. However, as described above, we plan to make the pre-analysis adaptive in the sense that it will receive information from the Correlator about threats observed elsewhere. Hence a substantial part of the research and performance optimisation regarding the network sniffers will focus on how existing principles can be used in an adaptive setup. In addition, we will investigate if further performance and/or precision can be achieved by utilising the available FPGAs.

Client Activity Monitoring

Client activity will be monitored by recording features related to changes in the file system, registry (or similar configuration database) and use of network connections in the individual hosts. This type of monitoring is comparable to what many client IDS systems already do. The collected features will be used as the basis for clustering analysis, and the results of this local analysis will be sent to the Correlators for further investigation of possible correlated activities in separate hosts. Research into performance optimisation of this process will be needed in order to reduce the computational load and storage requirements on the clients as far as possible, while retaining sufficient information for our analysis.

Client Distribution Analysis

A significant problem in many of the newest botnets is that malware may be distributed by non-traditional routes which will not be detected by traditional on-access AV scanning of mail and web access. Within the last few years, for example, distribution via Facebook spam, YouTube and on-line markets providing apps for smartphones has been observed, and there is every reason to believe that this trend will continue, expanding to cover other platforms. In addition, designers of malware now have access to almost unlimited computing power via cloud computing. This enables them to produce huge numbers of variants of each item of malware, so as to avoid malware collection and analysis by ensuring that each variant only appears very rarely and thus avoids rousing suspicion. We believe that correlation analysis, combined with in-depth post-analysis of harvested code, can mitigate this problem significantly, as we expect to be able to detect behavioural similarities among code items which appear not to be significantly related.

Correlation Framework

The Correlation Framework is one of the most important elements of our framework, as it should realize correlation of observation generated by various sensors. The Correlation Framework will be realized as two components: A Behavioural Analysis Component and a Trust Management Component.

The behavioural analysis component will analyse the filtered and pre-processed feature data provided by the client and network sensors, in order to search both for network-network and client-network correlations. It will further develop ideas proposed by a variety of research groups, as reported in Oliner et al. [START_REF] Oliner | Community epidemic detection using time-correlated anomalies[END_REF], Wang et al. [START_REF] Wang | Collaboration-based botnet detection architecture[END_REF][START_REF] Wang | Botnet detection architecture based on heterogeneous multisensor information fusion[END_REF], and Flaglien et al. [START_REF] Flaglien | Identifying malware using cross-evidence correlation[END_REF], amongst others. We intend to extend this previous work to cover more scenarios and platforms.

The trust management component has a task of assessing the trustworthiness of data and alerts from the different sensors within the system. Proposals for assessing the information received from the different sensors have been based on trust evaluation of the individual data sources [START_REF] Marsh | Formalizing Trust as a Computational Concept[END_REF], collaborative filtering techniques employing robust statistics [START_REF] Setia | Secure data aggregation in wireless sensor networks[END_REF] or extended with trust metrics [START_REF] Weng | Improving collaborative filtering with trust-based metrics[END_REF], or filtering to eliminate outliers in the received data [START_REF] Zhang | Outlier detection techniques for wireless sensor networks: A survey[END_REF]. None of these techniques, however, have been developed for the environment envisaged in the ContraBot infrastructure, where sensor data and alerts are shared among separate collaborating organisations. We therefore need to investigate hybrid techniques, where the results of the different filtering techniques are incorporated with different weights, e.g. the weight of the trust evaluation of the data provider is higher when evaluating input from end-users, because less can be assumed about their motives and competence levels.

The trust management component will assess the trustworthiness of the different sensors using both direct experience and indirect experience through a reputation system. Direct experience will be based on both content based filtering using data contained in the observations, such as the make, model and version of the sensor, and collaborative filtering where the output from one sensor is compared with output from other sensors in order to determine whether the sensor agrees with the majority. The trust management component will monitor the results of this trustworthiness assessment over time and apply the results to a trust evolution function, such as the one proposed for the Wikipedia Recommender System [START_REF] Jensen | Dynamics of trust evolution: Auto-configuration of disposiional trust dynamics[END_REF]. Moreover, the trust management component will build indirect trust in sensors by exchanging direct trust assessments (reputation scores) with the other trust management components in the Correlation Framework. This will significantly reduce the "cold start" problem and accelerate trust formation among components in the framework.

Testing

To facilitate tests of algorithms and architectural design, a closed and controlled Internetlike test network, in which experiments can be repeated, is needed. Based on the sniffing equipment, a testbed emulating a subset of the Internet will be designed and implemented. The testbed will facilitate botnet life cycle analysis with real and artificial bots, where spread patterns, infection times, etc. can be studied, both from a client and a network perspective. Furthermore, the testbed will facilitate the development of the client and network entities, as it will facilitate tests in realistic (emulated) conditions. It will also be used to test the scalability of given system architecture proposals. It may here prove possible to reuse substantial parts of the already existing emulab testbed system (http://www.emulab.com) with modifications. We believe that having a testbed on which the framework can be implemented and tested will allow us to achieve a precise, reliable and performance optimised product. Furthermore, as the threats evolve continually, it is important to have a test setup where updated mechanisms and parameters can be tested and evaluated.

Discussions and Future Work

In this paper we have presented an overview of existing botnet detection techniques and we have analysed their ability to cope with challenges of detecting modern botnets. Furthermore, we have shown that there is a need for new and more comprehensive detection approaches in order to provide efficient and effective neutralisation of botnets. Finally we introduced ContraBot a novel collaborative botnet detection approach.

To our best knowledge the ContraBot framework could possibly be the first extensive attempt to take counter botnet research to a systematic level, providing the basis for a more comprehensive botnet defence system. The botnet defence system envision by the ContraBot framework will aggregate simultaneous observations from different types of sensors, such as network sniffers and client monitors to identify suspect activities and possibly initiate appropriate counter measures.

The Contrabot framework is partly based on principles similar to existing collaborative botnet detection approaches such as [START_REF] Strayer | Botnet detection based on network behaviour[END_REF][START_REF] Oliner | Community epidemic detection using time-correlated anomalies[END_REF][START_REF] Flaglien | Identifying malware using cross-evidence correlation[END_REF][START_REF] Wang | Collaboration-based botnet detection architecture[END_REF][START_REF] Wang | Botnet detection architecture based on heterogeneous multisensor information fusion[END_REF], but it has a number of advantages: First, the ContraBot will employ traffic analysis in the core network, providing protection for a broader set of end-users. Secondly, our proposed set-up will combine information not only from network and client levels but also from in depth analysis of harvested code in order to improve the detection accuracy even further. Third, the proposed system will provide flexibility of including diverse end-user platforms through development of appropriate client-based analysis entities. Fourth, our system will also introduce the feed-back mechanism. This will provide adaptivity of network-and client-based pre-analysis entities to the bot-related information generated by correlating findings from other sources. This information allows the system to dynamically adapt to changes in behaviour of bots and botnets.

An important future step for testing and evaluating the framework is the development of a prototype system to demonstrate the technical approaches for reliable detection and elimination of botnets. Such a prototype system needs to be systematically evaluated using a suitable testbed. We believe a testbed should be developed specifically for this purpose, capturing salient features of large-scale networks. The prototype could be a first step twoards the development of a full-scale botnet defence platform.

Fig. 1 .

 1 Fig. 1. Architecture of the proposed analysis system.