Anne Coudrain
email: coudrain@ird.fr

Bernard Francou
email: bfrancou@acelerate.com

Zbigniew W Kundzewicz

Glacier shrinkage in the Andes and consequences for water resources-Editorial

INTRODUCTION

The state of mountain glaciers is a good climatic indicator of the global warming of the planet-one of most spectacular, and persuasive, manifestations of climate change. Numerous studies worldwide show a widespread, and well documented, retreat of mountain glaciers in non-polar regions of the world during the 20th century (IPCC, 2001). In fact, many glaciers have been shrinking for even longer, since the temperature minima of the Little Ice Age (17th-19th centuries), but a clear acceleration of the glacier retreat has been observed during recent decades. Glacier retreat is an undeniable fact and poses several questions: what is the reason for it and what are the observed and projected impacts? The likely reason is climate change and the primary impacts refer to glacier-based water resources and systems dependent on them. The glacier changes reflect mainly accumulated changes in temperature and precipitation. The relationship between glacier and temperature may depend on a number of factors, such as the geometry of the glacier and its surroundings, glacier area and depth, and those controlling the heat fluxes (summertime cloudiness, albedo, humidity, wind). On the global scale, air temperature is considered to be the most important factor controlling glacier retreat. For a typical mid-latitude glacier, a 1°C temperature rise would have the same effect as much greater decreases in cloudiness (by 30%) or precipitation (by 25%) (IPCC, 2001). In several areas, the climatic anomalies have been strongly influenced by the El Niño-Southern Oscillation (ENSO) events. The warm (El Niño) phase of ENSO, influencing the phase of precipitation at the altitudes of the glacier accumulation zone (for the Andes, see [START_REF] Francou | New evidences of ENSO impacts on glaciers at low latitude: Antizana 15, Andes of Ecuador, 0°28′[END_REF], has become more intense, more frequent, and more long-lasting in recent decades (IPCC, 2001).

Even if the general picture is of a widespread, and long-lasting, retreat of mountain glaciers, in a few regions glaciers were advancing, until a few years ago. In Norway, many coastal glaciers advanced in the 1990s due to precipitation enhancement related to the more pronounced positive phase of the North Atlantic Oscillation (NAO), but in the last four years, with very warm summers, glacier shrinkage has been observed.

Studies of the shrinkage of mountain glaciers have considerable potential to support or qualify the temperature records (IPCC, 2001). Climate-relevant glacier data, such as measurements of the terms of the surface energy balance, and measurements or reconstruction of the mass balance (gain or loss of ice mass) and of the geometry (area and length) of glaciers, complement the instrumental meteorological records. They are particularly valuable, as some of them extend back in time (to before the instrumental era) and some are from remote, inaccessible, data-scarce regions. Typically, glaciers exist at a significantly higher altitude than meteorological stations.

Tropical and sub-tropical areas are of particular concern. This is where most of the world's people live and where the wealth of global biodiversity is located. Unprecedented retreat of old glaciers in the tropics and sub-tropics has been observed and projections are made of complete disappearance of small glaciers. The iconic sites, such as Kilimanjaro, which was immortalized in Hemingway's novel -The Snows of Kilimanjaro‖, and Chacaltaya (Bolivia), which was the highest skiing station, may disappear completely in the near future.

Relating fluctuations in glacier mass balance to meteorological conditions is more complicated for tropical glaciers than for mid-and high-latitude mountain glaciers, since the most important factors may be those that drive the albedo and not the local temperature [START_REF] Sicart | Etude des précipitations et de la fonte sur un glacier tropical: le glacier duZongo, Bolivie, 16°S[END_REF]. Nevertheless, the fast glacier recession in the tropics appears to be consistent with an upward shift of the equilibrium line (where glacier accumulation balances with ablation) and of the 0°C isotherm.

ANDEAN GLACIERS

In contrast to the Alpine glaciers, which undergo a long accumulation period in winter and a short ablation season in summer, the glaciers of the tropical Andes experience, in their lower part, an ablation regime throughout the year. Melting is at its height in Bolivia and Peru during the austral summer (October-April) when the strongest radiation input coincides with the maximum rainfall, and in Ecuador in the months nearer to the equinoxes (April-May and September). Tropical Andean glaciers have a seasonal precipitation distribution (dry and wet season), while seasonal temperature variations are small, compared to strong diurnal (day-night) amplitude.

There is growing evidence that the observed general glacier retreat in the warming tropical Andes has accelerated significantly in the last decades. The retreat includes even large glaciers, but it is particularly dramatic for the small-sized glaciers, such as the Chacaltaya Glacier in Bolivia (16°S), whose present area (2005) is less than 0.04 km 2 . The Chacaltaya Glacier may disappear before 2010 (see Fig. 1). Along the length of the Andes, glacier retreats have been dominating and (minor) advances of glacier snouts have been exceptional. Data suggest that changes in precipitation and cloud cover in the latter part of the 20th century were minor, and that changes in these quantities are unlikely to explain the ubiquitous Andean glacier retreat. The general shrinkage of glaciers is driven by temperature rise at high elevation in the southern Andes. However, the processes are more complex in the tropics, where the increase in melting reflects a complex combination of factors related to the energy balance, such as temperature, duration of dry events, precipitation and humidity which control albedo, and melting/sublimation. balance, which is an estimate of the difference between the accumulation of snow and ice and their ablation (by melting and sublimation), appears to be strongly controlled by the climate variability at decadal time scales, driven by the ENSO mechanism. During the warm (El Niño) period, negative mass balances are observed in the tropical areas, linked to a deficit of precipitation during the summer/wet period in Bolivia and during February-May in Ecuador, which directly affects the albedo and the melting rates at the glacier surface. In this intense melting period, the snow/rain limit moves up to 5000 m, which results in decreased accumulation. Positive anomalies of mass balance are also documented during the warm (El Niño) period but generally occur on glaciers located in sub-tropical areas (30-35°S), due to enhanced winter precipitation. During an El Niño year, intertropical glaciers may lose from 600 to 1200 mm of water equivalent. The opposite occurs during the cooler and more humid La Niña phase, during which the glaciers return to equilibrium and sometimes show a minor increase. Warm events that have been occurring at higher frequency since the widely recognized shift in 1976, and the acceleration in the retreat of glaciers, particularly in the tropics, is seen as the consequence of the change in the Southern Oscillation regime and Pacific warming over the last 25 years. Between 1976 and 1997 the equatorial Pacific has been abnormally warm for more than 15 years, while cold conditions were more frequent during the 1956-1976 period (see http://www.cdc.noaa.gov/ENSO/enso.mei). As a consequence, the Andean glaciers showed a mass balance close to the equilibrium before 1976-1980, and a persistent negative balance thereafter.

It is important to identify the physical processes responsible for the surface melting and sublimation occurring on the glaciers. In a number of pilot studies, the energy balance of glaciers has been monitored and the amounts of energy received and absorbed by the glaciers, resulting from solar radiation and turbulent flow, were determined from meteorological data (including relative humidity, temperature, wind direction and velocity) collected at the glacier surface. The energy balance investigations show that glacier melt is governed mainly by the net radiation, which represents the fraction of incident solar radiation absorbed by the glacier. This emphasizes the essential role of the reflective properties of the glacier surface, i.e. the albedo. As noted by [START_REF] Sicart | Etude des précipitations et de la fonte sur un glacier tropical: le glacier duZongo, Bolivie, 16°S[END_REF], melting of tropical glaciers strongly depends on the seasonal distribution of precipitation, due to the high albedo of (even thin) fresh snow cover.

The present Special Section of Hydrological Sciences Journal contains six papers referring to tropical and sub-tropical glaciers in four countries of South America: Bolivia, Chile, Ecuador and Peru. These are revised and updated versions of selected contributions to the Second Symposium on Mass Balance of Andean Glaciers. The symposium, organized by INRENA (Instituto Nacional de Recursos Naturales, Peru) and IRD (Institut de Recherche pour le Développement, France), was held in Huaráz (Peru) from 6 to 9 July 2004. It was co-sponsored by the International Association of Hydrological Sciences (IAHS). The main purpose of this event was to highlight the recent climatic changes occurring in the Andean Cordillera and to encourage the scientific community to strengthen the glacier observation network existing along the Andean chain from Colombia to the Patagonian ice fields. Abstracts of all the papers presented at the Huaráz Symposium and authors' addresses are available at http://www.greatice.ird.fr. [START_REF] Carrasco | Changes of the 0°C isotherm and the equilibrium line altitude in centralChile during the last quarter of the 20th century[END_REF] report an overall retreat of glaciers in the Andes of central Chile during the last hundred years, probably due to changes in temperature and precipitation. An overall warming, of 1.3-2.1ºC in minimum near-surface air temperature and 0.2-1.5ºC in maximum temperature, occurred in central Chile during 1961-2001. Analysis of radiosonde temperature data for central Chile shows mid-tropospheric warming with an increase in elevation of the 0ºC isotherm of 122 ± 8 m and 200 ± 6 m in winter and summer, respectively, during 1975-2001. Precipitation data show a general decrease during the last century and a slight increase during the second half of the 20th century in a latitude range 30-34°S. This behaviour is probably due to the influence of the ENSO, which is stronger northward of 34ºS. Warming has been concentrated during periods with no precipitation, leading to enhanced melting of glaciers. The number of days with precipitation has decreased, indicating that precipitation events are becoming less frequent but more intense. This also suggests that glaciers are exposed to more days with atmospheric conditions appropriate for melting. [START_REF] Carrasco | Changes of the 0°C isotherm and the equilibrium line altitude in centralChile during the last quarter of the 20th century[END_REF] make projections for the end of the 21st century, which indicate that the equilibrium line altitude in central Chile (30-38ºS) may rise by about 400 m compared to its present-day location, under SRES scenario A2 (cf. IPCC, 2000). Changes in air temperature rather than precipitation are projected to be the main driving factor. [START_REF] Jordan | Estimation by photogrammetry of the glacier recession on the Cotopaxi Volcano (Ecuador) between 1956 and 1997[END_REF] used aerial photographs of the Cotopaxi Volcano ice cap (Ecuador) to quantify the evolution of the surface area. The results show that glaciers stagnated from 1956 to 1976 and then underwent a very strong recession from 1976 to 1997, losing about 30% of their surface area (probably linked to the increase in intensity, duration and frequency of warm ENSO phases). This finding corroborates the observations made on the nearby Glacier 15 (Antizana ice cap) located 10 km northeast of the Cotopaxi Volcano, which also lost about 30% of its surface area from 1956 to 1997. Slope exposure to humid fluxes from the Amazon and solar radiation at the Cotopaxi ice cap did not have any significant effect, since all the glaciers of the volcano retreated to a similar degree. It is interesting to note that the glacier recession on the Cotopaxi Volcano was particularly pronounced because of the conical form of the ice cap, resulting in exposure of the surface area below the equilibrium line altitude to strong ablation conditions. [START_REF] Rivera | Glacier shrinkage and negative mass balance in theChilean Lake District (40°S)[END_REF] found that ice-capped volcanoes of the Chilean Lake District have undergone significant glacier retreat during recent decades, probably in response to tropospheric warming and precipitation decrease. By 2003, the shrinking glaciers of the Mocho-Choshuenco Volcano had lost 11.5 ± 2.5 km between 1987 and 2003. The influence of ashes originating from the nearby Villarrica Volcano on the glacier dynamics of the (presently inactive) Mocho-Choshuenco Volcano are presumably negligible, because the dominant winds dispersed the volcanic material ejected by Villarrica far away from Mocho-Choshuenco. Therefore, observed ice-area changes on this volcano are thought to be driven mainly by climatic factors. [START_REF] Mark | Hydrochemical evaluation of changing glacier meltwater contributionto stream discharge: Callejon de Huaylas, Peru[END_REF] estimated the glacier melt contribution to streamflow in the Cordillera Blanca, Peru, over different spatial scales, using water balance and endmember mixing computations. The glacierized Cordillera Blanca has undergone an overall reduction in glacier volume throughout the 20th century. Water balance studies show elevated discharge in recent years, when glacial melt accounted for most of the annual mean discharge, which is considerably more than before. On average, the discharge of the Rio Santa leaving the Callejon de Huaylas (8% glacierized) is estimated as a mixture with 66% deriving from glacierized tributaries of the Cordillera Blanca and the rest from the non-glacierized Cordillera Negra.

As noted by [START_REF] Mark | Hydrochemical evaluation of changing glacier meltwater contributionto stream discharge: Callejon de Huaylas, Peru[END_REF], the Yanamarey Glacier catchment in the southern Cordillera Blanca, 75% of which is covered by glacier ice, is representative of small glaciers in the range, and its recession in recent years has been very extensive. The multi-decadal rates of terminus recession have accelerated four-fold from 5 m year 2005) demonstrates the validity of the empirical relationship obtained between the air temperature ranges and the percentages of snowfall occurrence, useful in hydrological modelling. Determining the precipitation phase-rain or snow-is an important factor in modelling discharge in mountainous basins. In a study carried out in the outer tropical Andes of Bolivia, half-hourly determination of precipitation phase was obtained and relationships were studied between the determined precipitation phase and observed air temperature. The main result of this comparative study, based on precipitation data from the Andes and the Swiss Alps, is the good similarity between the relationships of snowfall occurrence percentages and air temperature in these two mountain ranges, in spite of the differences in climate and altitude. [START_REF] Pouyaud | Avenir des ressources en eau glaciaire de la Cordillère Blanche[END_REF] examined hydrological data in the Llanganuco basin (87 km 2 , 39% glacierized), Cordillera Blanca, Peru and found a long-term increase in glacial melting during the last quarter of the 20th century. The basin runoff was found to be well correlated to the atmospheric temperature. This finding agrees with the observation of retreat of several other glaciers in the Cordillera Blanca, which has been well documented for 50 years, with accelerated shrinkage since the mid-1970s. A model is presented allowing computation of the future evolution of the melt runoff for several catchments, which predicts the occurrence of a maximum discharge followed by a regular decrease for the next century as the temperature increases and the ice reservoir shrinks.

IMPACTS ON WATER RESOURCES

Glaciers play a very important role in global freshwater storage-69.6% of the world's freshwater (nearly 25 million km 3) is stored in glacial ice. The mountain glaciers allow for large volumes of atmospheric precipitation to be stored and then released gradually into river networks throughout warm or dry seasons. For the mid-and low-latitude regions, the equivalent water volume of the glacial ice is 0.2 million km 3 , that is over 100 times more than that of the rivers (0.0017 million km 3 ). Mountain glaciers are old natural water reservoirs. The mean global sojourn time of a water particle in a mountain glacier is of the order of 1600 years.

Many large rivers of the world originate in mountainous areas. The high mountains -the Himalayas, the Andes and the Alps-with their glaciers, are the world's virtual water towers, assuring year-round water flows. In the dry Andes, glacial meltwater constitutes river flow during the long dry season. The rapid shrinkage of the mountain glaciers threatens the livelihoods of many people and the future of ecosystems, with numerous rare and endemic species.

The melting of glaciers may lead to water shortages for millions of people. Among the regions most at risk from glaciers melting due to climate change are: Bolivia, Ecuador and Peru (cf. contributions in this Special Section), where glaciers feed rivers all year round. On the Pacific side of Peru, 80% of the water resources originate from snow/ice melt. Often, glacier-fed surface waters constitute the sole source of water, not only for rural areas but also for major cities (water supply and hydroelectric power). Many basins, including large areas of glaciers in the cordilleras, have experienced an increase in runoff in recent decades, while precipitation has not changed, or tended to decrease. This can be interpreted as the consequence of glacier retreat-there may be more water in the rivers, but at the cost of reduction in the storage of frozen water in the glaciers. Hence, the recent increase in runoff is not likely to last very long. This is not good news for future generations-it raises sustainability concerns.

For instance, ongoing and rapid glacier recession in the Cordillera Blanca was found to have enhanced discharge at the expense of catchment storage [START_REF] Mark | Hydrochemical evaluation of changing glacier meltwater contributionto stream discharge: Callejon de Huaylas, Peru[END_REF][START_REF] Pouyaud | Avenir des ressources en eau glaciaire de la Cordillère Blanche[END_REF]. The glaciers now appear to be in persistent negative mass balance. Seasonal stream runoff may become more variable in the future, as peak discharge coincides with highly seasonal peak precipitation. Short-term increases in stream discharge with critical long-term loss of storage are likely to be widespread over the Cordillera Blanca region. Since glacier melt provides a very significant proportion of discharge of the Rio Santa, the latter is also likely to diminish if glaciers continue to melt.

Rapid melting of glaciers can lead to flooding of rivers and to the formation of glacial meltwater lakes, which may pose the serious threat of dynamic outburst floods, caused by continued melting or calving of ice chunks into lakes. The Cordillera Blanca, with more than 1000 lakes formed by recent glacial retreat, is an area at risk of outburst of moraine-dammed lakes.

FINAL REMARKS

The contributions to this Special Section illustrate the ongoing change in the state of tropical glaciers in the Andes. There is a general observation of widespread glacier retreat that is considerably more rapid since the mid-1970s. However, even if the temperature rise is responsible for much of the accelerated shrinking of tropical and sub-tropical glaciers, there are also other factors that need to be taken into account in order to explain the observed deglaciation.

The causes of tropical glacier retreat are being debated in a vigorous, international discussion. Despite shrinking funds for observation networks, it is of utmost importance to maintain, and possibly enhance, the monitoring programmes in data-scarce tropical glacier areas and to collect documentation of the ongoing changes in order to improve understanding. Programmes of observations, such as those reported in this Special Section, and in [START_REF] Sicart | Etude des précipitations et de la fonte sur un glacier tropical: le glacier duZongo, Bolivie, 16°S[END_REF] and [START_REF] Røhr | Rainfall distribution on the slopes of Mt Kilimanjaro[END_REF], deserve applause.

It is necessary to continue the mass balance monitoring programmes at Andean glaciers in order to verify the recent trends and their representativeness. Field measurements need to be complemented with satellite observations, as well as modelling studies, in order to improve our understanding of glacier dynamics.

The International Association of Hydrological Sciences welcomes the fact that a wealth of important material on the Andean glaciers and their water resources is published in the present issue of Hydrological Sciences Journal. This is the first time that this remote region has been selected as a topic for a Special Section of HSJ. The six papers herein have been largely prepared by experts from four Andean countries: Bolivia, Chile, Ecuador and Peru, with co-authors from Europe and the USA.

The principal objective of the IAHS is to promote the study of hydrology as an aspect of the Earth sciences and of water resources, and, in particular, to study the hydrological cycle on the Earth, including snow and ice. The Association's area of interest embraces physical, chemical and biological processes, their relationship to climate and to other physical and geographical factors, as well as the interrelations between them. The present Special Section is a valuable contribution towards fulfilling the IAHS objectives.

  study by L'Hôte et al. (

Coincidentally, earlier this year, the former International Commission on Snow and Ice (ICSI) of IAHS became the Commission of Cryospheric Sciences of IUGG (CCS) and should become a full IUGG Association in 2007. We wish ICSI colleagues success in their new endeavour. As demonstrated by the papers in this Special Section, snow and ice play an important role in the hydrological cycle, being of particular importance for water resources. In recognition of this, a new IAHS commission devoted to snow and ice hydrology, the International Commission on Snow and Ice Hydrology (ICSIH) was launched during the IAHS Assembly in Foz do Iguaçu, Brazil, in April 2005 and a provisional Bureau has been appointed (see http:www.iahs.info for details).

Acknowledgements

Anne Coudrain and Bernard Francou acknowledge the institutions of Andean countries that contribute significantly to the Great Ice Programme of IRD. The authors wish to acknowledge the main contributing institutions, namely Instituto Hidráulica e Hidrología, Universidad Mayor de San Andres and Servicio Nacional de Meteorología e Hidrología in Bolivia; Centro de Estudios Científicos (CECS) in Chile; Instituto Nacional de Meteorología e Hidrología (INAMHI) in Ecuador; and Servicio Nacional de Meteorología e Hidrología (SENAMHI) and Instituto Nacional de Recursos Naturales (INRENA) in Peru. Z. W. Kundzewicz acknowledges the German Science Foundation (DFG), who financed his visit to Bolivia.


André De Palma

Robin Lindsey

Guillaume Monchambert Optimal

Lindsey

Optimal fares and capacity decisions for crowded public transport systems

come   L'archive ouverte pluridisciplinaire

Introduction

Crowding on urban mass transit systems is common in both developed and developing countries. A roundtable report by the International Transport Forum identifies crowding as a major source of inconvenience that increases the generalized cost of travel (OECD, 2014). Crowding occurs not only while riding buses and trains, but also when boarding and alighting from them, when purchasing tickets, while waiting on platforms or at stops, and while accessing stations by escalator, elevator or on foot (King et al., 2014).

Several recent studies have documented the cost of crowding on transit networks. For example, Prud'homme et al. (2012) estimate that the 8% increase in densities in the Paris subway between 2002 and 2007 imposed a welfare loss of at least €75 million per year. Veitch et al. (2013) estimate the annual total cost of crowding in Melbourne metropolitan trains in 2011 at $280 million. Tirachini et al. (2013) provide a detailed review of the extensive literature on public transport crowding. Studies find that crowding increases in-vehicle time and waiting time, reduces travel time reliability, and causes stress and feelings of exhaustion. A number of studies document how disutility from in-vehicle time increases with the number of users.

Lindsey 2

There is a large operations research literature on public transit system design. An extensive economic literature has also developed on public transit capacity investments, service frequency, and optimal pricing and subsidy policy. These two branches of literature have made significant advances in understanding public transit systems. However, in contrast to the literature on automobile traffic congestion, most of the studies have employed static models that cannot account for travelers' time-of-use decisions and the dynamics of transit congestion and crowding.

The time profile of ridership is driven by the trade-off that users face between traveling at peak times and suffering crowding, and avoiding the peak by traveling earlier or later than they would like. A few studies 2 have explored this trade-off using simple microeconomic models that combine trip-scheduling preferences as introduced by Vickrey (1969) with a crowding cost function that describes how utility from travel decreases with passenger loads. In this paper we use this modeling framework to analyze usage of a rail transit line, and assess the potential benefits from internalizing crowding externalities by setting differential train fares. We also present results on optimal train capacity and the number of trains put into service.

The model

Consider a transit line that connects two stations without intermediate stops. The line operates on a timetable to which the operator adheres precisely. There are m trains, indexed in order of departure. Train k leaves the origin station at time k t . The time headway between successive trains is a constant, h, so that 1

kk t t h  , 1,..., 1 km  .
The headway is set at the minimum feasible value consistent with safe operation. Travel time aboard a train is independent of both departure time and train occupancy, and without loss of generality it is normalized to zero. Each train therefore arrives at the destination as soon as it leaves the origin station.

Each morning, a fixed number, N, of identical individuals use the line to get to work. Users know the timetable, and have to choose which train to take. They prefer to reach the destination at a common time, Lindsey 3 * t . If they arrive before * t , they incur a disutility or "schedule delay costˮ of  per minute they are early. For late arrival the penalty is  per minute. Hence, the schedule delay cost of taking train k,  

k t  , is (1)
  ** , 1,..., k k k t t t t t k m                  ,
where

  max 0, xx  
. Users are assumed to board a train in random order, and (as in de Palma et al., 2015) thus cannot increase their chance of securing a good seat by arriving at the origin station early.

The expected cost of crowding is   gn, where n is the number of users taking the same train. Function   gn is an average over possible states: securing a good seat, getting a bad seat, having to stand in the middle of the corridor, standing close to the door, etc.. In this paper we assume that  

k k k k n c t t t t k m s                  
User equilibrium with a uniform fare In this subsection we derive and characterize user equilibrium (UE) when N is fixed, and the fare is uniform; i.e. the same for all trains. A uniform fare does not affect either the division of users between trains or crowding costs. Let e c denote the equilibrium trip cost net of fare, and e k n equilibrium ridership on train k. In UE, users distribute themselves between the m trains so that the user cost net of fare on every train is e c . Given eq. (1) this implies (2)   , 1,..., . Since every user has to take some train,

.

m e k k nN    Lindsey 4
Equilibrium ridership is solved by substituting eq. ( 2) into (3):

(4) In equilibrium, total schedule delay costs are lower than if users were equally distributed across trains (in which case e SDC N   ) because users crowd onto timely trains that arrive closer to * t . Total crowding costs are higher by the same amount, so that total costs are the same as if users were equally distributed.

  2 e s SDC N m       , (7)   2 2 e Ns TCC m ms        , (8) 2
We now derive the optimal uniform fare. The equilibrium private cost of a trip, e p , equals the user cost plus the fare,  : Lindsey 5 ( 9) . From eq. ( 8), the marginal social cost of a trip is:

(10) 2 . e e TC N MSC N ms       
The first term in ( 10) is the same as in ( 5). The second term is proportional to N, and it is twice the corresponding term in (5) because the marginal social cost of crowding is twice the average cost. The average external cost is With elastic demand, considered later, it is optimal to charge a uniform fare equal to the average external cost:

(11) , u N ms   
where superscript "uˮ denotes the uniform-fare optimum. Total revenue from the optimal uniform fare is



The uniform fare does not support the social optimum because the marginal external cost of crowding varies with train occupancy, and it is larger on more heavily used trains. The social optimum is examined in the following subsection.

Social Optimum

In the social optimum (SO), the marginal social cost of trips is the same on all trains. The marginal social cost of using train k is

    . kk k kk k cn n MSC t ns        
Let superscript "oˮ denote the SO, and o MSC the marginal social cost of a trip. At the optimum, Lindsey 6

(14)   , 1,..., . o k kk n MSC t MSC k m s       
Since every user takes some train, the counterpart to eq. ( 3) holds:

(15

) 1 . m o k k nN   
Solving eqs. ( 14) and ( 15) one obtains ( 16) 16) and ( 4) that train loads in the SO are more even than in the uniform-fare equilibrium. Spreading users is desirable because the cost of crowding is a quadratic function of load, and the benefits from reducing loads on timely trains exceed the costs of greater crowding on other trains.

  , 1,..., 2 o kk Ns n t k m m         , (17) 2 . o N MSC ms    It is evident from eqs. (
The SO usage pattern can be decentralized by charging a fare on train k equal to the marginal external cost of usage. We will call this fare pattern the SO-fare. The marginal external cost of usage on train k is , 1,..., .

k k k k n MEC MSC c k m s     
The SO-fare on train k is therefore:

(18)   , 1,..., . 2 o k o k k t n N km s ms         
Compared to the uniform fare in eq. ( 11), the fare in ( 18) is higher on timely trains and lower on the earliest and latest trains. Users of all trains incur a private cost equal to the social cost of a trip: 2 , 1,..., .

o o o o k k k N p c MSC k m ms        
The private cost is the same as the cost with the uniform fare in eq. ( 13). It is higher than the cost if no fares are charged. To see this, note that at least one train is more crowded in the SO than the UE. Compared to the UE, in the SO a rider of this train incurs the same schedule delay cost, but a higher crowding cost and a positive fare. Since all users incur the same private cost in the UE, and all users incur the same private cost in the SO, private costs are higher in the Lindsey 7 SO. Unless fare revenues are used to improve service in some way, charging fares to price crowding costs leaves users worse off.

Total revenue from the SO-fare is

1 m o o o kk k Rn    
. Using eqs. ( 16) and ( 18) one obtains

(19)   2 2 . 4 o Ns Rm ms       
The first term in ( 19) matches revenue from the optimal uniform fare in (12). The second term is extra revenue due to variation of the fare. This will be called variable revenue, o RV , where 3 (20) (23) .

      2 2 2 3 2 . 4 48 o s s RV m h m            Other
o e o
TC TC RV  Total schedule delay costs are higher in the SO than the uniform-fare or no-fare equilibrium. However, crowding costs are smaller by 1.5 as much, and total costs are lower by variable revenue.

As indicated in eq. ( 20), variable revenue is independent of N. The welfare gain from setting optimal fares is therefore independent of total usage. This may seem surprising since intuition would suggest that the welfare gain increases with N: first because crowding becomes more onerous for users on average, and second because more users suffer the higher cost. To understand the result, recall that the welfare gain arises from distributing users more evenly between trains. Since the difference in crowding costs between two successive trains equals the difference in schedule delay costs, the benefit from reallocating users between trains is independent of N. As N increases, marginal crowding costs on each train rise at the same rate. The uniform-fare component of the optimal toll in eq. ( 18) increases linearly with N, but the variable component does not change.

Lindsey 8

Another way to view the result is in terms of total costs. The marginal social costs of usage in the UE and SO are given in eqs. ( 11) and ( 17) respectively. Since the equations are the same, the marginal social costs are the same. In effect, the benefits of internalizing the crowding cost externality are exhausted once total usage is large enough for all trains to be usedas assumed throughout the paper.

In a longer version of this paper (de Palma, Lindsey and Monchambert, 2015) we have shown that the welfare gains from congestion pricing depend on the shape of the crowding cost function,

  . g . If   . g
is convex, the welfare gain decreases with N, and if

 

. g is concave, the welfare gain increases with N. Most empirical studies find that   . g is either linear or convex. This suggests that the benefits of differentiating fares by train (or, equivalently, time of day) may be limited on heavily used transit systems. The model thus offers one explanation for why peak-load pricing on transit systems is not very common.

Optimal transit service with elastic demand

We now turn attention to the long run when the transit authority can choose the number of trains, m, train capacity, s, and the train timetable. We continue to assume that all trains have the same capacity, and that the headway is uniform and exogenous. When the schedule delay and crowding cost functions are linear, as assumed, the optimal timetable is straightforward to derive and, due to space constraints, it is not described here.

To investigate the optimal values of m and s we assume that the capital, operations and maintenance costs of providing service are described by a function   , K m s which is strictly increasing in m and s. To facilitate analysis, m will be treated as a continuous variable.

We now allow total usage to depend on the price, defined in eq. ( 9), and let   smaller than this because the improved service quality attracts new users. Because usage is underpriced, the increase in usage is welfarereducing which shrinks the benefit from greater capacity. This latent demand effect accounts for the second term of the product on the lefthand side of (25) which is less than 1. In the limit of perfectly elastic demand (i.e., 0 N p  , the potential benefit is completely dissipated. In the opposite limit of fixed demand (i.e., N p   ), the second term converges to 1, and there is no dilution of benefit. Equation ( 26) for m is interpreted similarly. The first term in brackets on the left-hand side is the marginal benefit from less crowding. The second term in brackets is the marginal disbenefit due to greater schedule delay costs. This net benefit is diluted by the same factor as in eq. ( 25). With the optimal uniform fare, the first-order conditions work out to:

(27) 2 2
For with optimal uniform fare : ,

s N sK ms   (28) 2
For with optimal uniform fare : .

m N m N K m ms       

Lindsey 10

In contrast to eqs. ( 25) and ( 26), the marginal benefits from expanding service in eqs. ( 27) and ( 28 With the SO-fare, social surplus net of capacity costs is given by ( 29) 29) is the same as eq. ( 24) except for the last term, o RV , which is a function of m and s, but does not depend on N. Since usage is priced efficiently in both the SO-fare and optimal uniform-fare regimes, the first-order conditions for s and m are the same as for the optimal uniform toll, ( 27) and ( 28 30) and ( 31) are smaller than their counterparts for the optimal uniform toll, ( 27) and ( 28). The generation of variable revenue from the SO-fare effectively reduces the marginal financial cost of expanding capacity. In the case of (30) this implies that optimal train capacity conditional on the values of m and N is larger in the SO: 

      2 0 , , N oo n N SS p n dn N K m s RV m s ms             . Equation (
   ** ,, ou s m N s m N  .
Similarly, eq. ( 31) implies that the optimal number of trains conditional on the values of s and N is also larger in the social optimum:

    ** ,, ou m s N m s N  .
These rankings may seem surprising given that total system costs are lower in the SO than the uniform-fare equilibrium. Inequality

    ** ,, ou m s N m s N 
is explained by the fact that ridership is distributed more evenly across trains in the SO. More users take the earliest and latest trains in the SO which makes adding extra trains more beneficial. The reason for the inequality

    ** ,, ou s m N s m N 
is more subtle. It can be shown that while total user costs in the uniform-fare regime decrease with s, the deadweight loss from imbalanced ridership between trains increases with s. Expanding capacity is therefore more valuable in the social optimum. By contrast, in the Vickrey (1969) bottleneck model of road traffic congestion, optimal capacity is higher with a uniform fare.

A numerical example

Further properties of the model are difficult to derive analytically, and to proceed further we now adopt a specific capacity function that is based on Kraus and Yoshida ( 2002

): (32)     0 1 2 , K m s s m s       ,
where 0 v , 1 v and 2 v are all nonnegative parameters. The term 01 s   in (32) is the incremental cost of running an additional train, which includes both capital and operating costs. It is a linear increasing function of train capacity. If 0 0 v  , there are scale economies with respect to train size. The second term in (32), 2 s  , accounts for costs that depend on train capacity, but not the number of trains, such as terminal capital costs.

The numerical example draws on recent empirical estimates of crowding costs, and is loosely calibrated to describe service on the Paris RER A line during the morning peak. 1.

With no fare, the equilibrium private cost (which equals the equilibrium user cost) is €4.54. There are n N =21,500 users who are accommodated in * n m =25.27 trains with (nominal) capacities of * n s =811. Total crowding costs are more than double total schedule delay costs. Capital costs ( n K ) amount to a little over 60% of total user costs ( n TC ). Given no fare, cost recovery,  , is zero.

The optimal uniform fare works out to u  = €2.65. It boosts the equilibrium private cost to u p = €6.90 which is €2.36 above the no- fare equilibrium price. Ridership drops to u N =18,700 which is 13% below the no-fare level. Both the number of trains and train capacity are also lower than with no fare although capacity costs are reduced by only 2.8%. Total crowding costs and total schedule delay costs are also lower than with no fare. Consumers' surplus is lower than with no fare, but social surplus is higher by €4,135 or about €0.22 per rider in the uniform-fare equilibrium. The relative efficiency of the optimal uniform fare can be measured as a fraction of the difference in social surplus between the SO and the no-fare equilibrium. It works out to about 0.82 so that the optimal uniform fare yields most of the efficiency gains from the SO-fare.

The SO features more trains than either the no-fare or the uniformfare regime. However, train capacity is slightly lower than in the other two regimes. Ridership and consumers' surplus are slightly higher than with a uniform fare, whereas price, revenue per user and cost recovery are slightly lower. Crowding costs are significantly lower than in the other two regimes, but schedule delay costs are higher than with a uniform fare because the SO-fare spreads usage more evenly over trains.   , the optimal uniform-fare yields a much higher welfare gain of €0.42. The welfare gain from the SO increases too to €0.51, and the relative efficiency of the uniform-fare regime is little changed.

Conclusion

In this paper we have studied the time profile of ridership on a crowded rail transit line. We solve for the user equilibrium and social optimum when supply is fixed, as well as the long run when service can be optimized. Some of the results parallel those obtained with road traffic congestion models. Passenger loads are distributed more evenly across trains in the social optimum than the user equilibrium.

The social optimum can be decentralized by charging higher fares on more popular trains to internalize the crowding cost externality on each train. Imposing differentiated fares makes users worse off ---at least before accounting for how the revenues are used. Other results are less obvious. The welfare gains from tolling are independent of total ridership. Expanding the number of trains can also be more valuable in the social optimum than the user equilibrium even though total system costs are lower in the social optimum.

Bibliography

  capacity. The linear form is supported by the metaanalysis of Wardman and Whelan (2011). Let k n denote the number of users on train k. A user taking train k incurs a combined schedule delay and crowding cost of

K

  pN denote the inverse demand curve. With a uniform fare, social surplus net of capacity costs chooses m and s to maximize e SS . With a zero fare, the first-order conditions work out to: are derivatives of   , K m s with respect to s and m respectively. The first term of the product on the left-hand side of (25) is the marginal benefit from expanding train capacity if usage remained fixed. The average cost of crowding would decrease by N users. The actual reduction in crowding is

  ) are not diluted by additional usage because usage is priced efficiently. This might suggest that the optimal values of s and m, , at least for given values of s and m, usage is higher in the no-fare regime because the private cost of usage is lower. This leaves the rankings of * ambiguous in general.

  with respect to s and m respectively. The right-hand sides of eqs. (

  4 Base-case parameter values are:  =5 [€/(hr⋅user)],  =20 [€/(hr⋅user)],  =2.72 [€/user], and h=2 [min/train]. The demand function is assumed to have a constantfare revenue equal to 5/6 of capacity costs. The resulting values are: 0 N =35,598, 0 v =412.8, 1 v =0.5058 and 2 v =49.78. Results for the three fare regimes are reported in Table

de

  Palma, A., Kilani, M., and Proost, S. (2015), Discomfort in mass transit and its implication for scheduling and pricing, Transportation Research Part B, 71(1), 1-18. de Palma, A.,Lindsey, R., and Monchambert, G. (2015), The economics of crowding in public transport. Working paper. Huang, H.J., Tian, Q., and Gao, Z.Y. (2005), An equilibrium model in urban transit riding and fare polices, Lecture Notes in Computer Science, 3521, 112-121. King, D., Srikukenthiran, S., and Shalaby, A. (2014), Using simulation to analyze crowd congestion and mitigation at Canadian subway interchanges: case of Bloor-Yonge Station, Toronto, Ontario, Transportation Research Record, 2417, 27-36. Kraus, M., and Yoshida, Y. (2002), The commuter's time-of-use decision and optimal pricing and service in urban mass transit, Journal of Urban Economics, 51(1), 170-195.

  aggregate costs in the SO work out to:

	(21)	SDC	o	2 , e o SDC RV
	(22)	3 RV , e o TCC TCC o

  Capacity costs are intermediate between the

	other two regimes. Social surplus is higher than with no fare by about
	€0.27 per rider.
		Fare regime
		No-fare (n )Opt. uniform (u ) Social opt. (o )
	m	25.27	24		25.69
	s	811	800		787
	N	21,500	18,700	18,814
	p	4.54	6.90		6.77
	Rev/user	0.00	2.65		2.63
	TCC	68,493	55,563	49,424
	SDC	29,092	23,896	28,588
	TC	97,584	79,459	78,012
	K	61,164	59,447	60,029
	R	0	49,539	49,424
	ρ	0	0.833 0.823324901
	CS	1,004,019	956,898	959,244
	SS	942,856	946,990	948,638
	Gain/N u		0.22		0.27
	Rel.eff	0.00	0.822		1
	Table 1: Comparison of no-fare, optimal uniform fare, and SO-fare
	(i.e., social optimum) regimes: base-case parameter values
	The number of trains has been treated as a continuous variable
	although it is discrete in reality. The model was resolved by
	restricting m to integer values to obtain * n m =25 and * o m =26. Results
	were hardly affected, and social surplus was virtually unchanged.
	To test the sensitivity of the results to the demand function, solutions
	were derived with different values of the elasticity. With	0   , the
	uniform fare yields no welfare gain at all and merely transfers money
	from users to the transit authority. The SO-fare yielded a welfare gain
	of only €0.097 compared to €0.27 in the base case. With		2 / 3
		13		Lindsey

surplus between regimes, the area under the demand curve is computed for p≤ €100.


Brahim Hamid
email: hamid@irit.fr

Christian Percebois
email: percebois@irit.fr

Model-Based Specification and Validation of Security and Dependability Patterns

Keywords: Pattern, Meta-model, Domain, Formalization, Model driven engineering, Security and Dependability

The requirement for higher Security and Dependability (S&D) of systems is continuously increasing, even in domains traditionally not deeply involved in such issues. In our work, we propose a modeling environment for pattern-based secure and dependable embedded system development by design. Here we study a general scheme for representing security and dependability (S&D) design patterns whose intention specification can be defined using a set of local properties. We propose an approach that associates Model Driven Engineering (MDE) and formal validation to get a common representation to specify patterns for several domains. The contribution of this work is twofold. On the one hand, we use model-based techniques to capture a set of artifacts to specify patterns. On the other hand, we introduce a set of artifacts for the formal validation of these patterns in order to guarantee their correctness. As an illustration of the approach, we study the authorization pattern.

Introduction

Extra-functional concerns have become a strong requirement on one hand, and on the other hand more and more difficult to achieve, even in safety critical systems. They can be found in many application sectors such as automotive, aerospace and home control. Such systems come with a large number of common characteristics, including real-time, temperature, computational processing and power constraints and/or limited energy and common extra-functional characteristics such as dependability and security [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF] as well as efficiency.

The integration of such concerns, for instance security, safety and dependability, requires the availability of both application development and concerns expertise at the same time. Therefore, the development of such systems involves specific software building processes. These processes are often error-prone because not fully automated, even if some level of automatic code generation or even model driven engineering support is applied. Furthermore, many critical systems also have assurance requirements, ranging from very strong levels, involving certification (e.g., DO178 and IEC-61508 for safety relevant embedded systems development), to lighter levels based on industry practices.

Over the last two decades, the need for a formally defined safety lifecycle process has emerged. Model-Driven Engineering (MDE) [START_REF] Schmidt | Model-driven engineering[END_REF] provides a very useful contribution for the design of these systems, since it bridges the gap between design issues and implementation concerns. It helps the designer to specify in a separate way extra-functional requirements at a higher level which are important to guide the implementation process. Of course, an MDE approach is not sufficient but offers an ideal development context. Hence capturing and providing this expertise by the way of specific patterns can enhance safety critical systems development. While using an MDE framework, it is possible to help concerns specialists in their task.

In this paper, we investigate the design process of Security and Dependability (S&D) patterns. The main goal of this work is to define a modeling and development framework to support the specifications and the validation of S&D patterns and to assist the developers of trusted applications for resource constrained embedded systems. The solution envisaged here is based on combining metamodeling techniques and formal methods to represent S&D pattern at two levels of abstraction fostering reuse during the process of pattern development and during the process of pattern-based development. The contribution of this work is twofold: [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF] An S&D pattern modeling language to get a common representation of S&D patterns for several domains in the context of embedded systems using model driven software engineering, (2) Formal specification and validation of a pattern in order to guarantee its correctness during the pattern integration. Therefore, patterns can be stored in a repository and can be loaded in function of their desired properties. As a result, patterns will be used as bricks to build applications through a model driven engineering approach.

The rest of this paper is organized as follows. An overview of the modeling approach we proposed including a set of definitions is presented in Sect. 2. Then, Sect. 3 presents in detail the pattern modeling language. Section 4 illustrates the pattern modeling process in practice. Section 5 presents the validation process through the example of the authorization pattern. In Sect. 6, we review most related works addressing pattern specification and validation. Finally, Sect. 7 concludes this paper with a short discussion on future works.

Conceptual Framework

We promote the separation of general-purpose parts of the pattern from its required mechanisms. This is an important issue to understand the use of patterns to embed solutions targeting extra-functional concerns. This section is dedicated to present the pattern modeling framework. We begin with a set of definitions and concepts that will prove useful in understanding our approach.

Definitions and Concepts

In [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF], a design pattern abstracts the key artifacts of a common design structure that make it useful for creating a reusable object-oriented design. They proposed a set of design patterns for several object-oriented design problems. Several generalizations on this basis to describe software design patterns in general are proposed in literature. Adapting the definition of security patterns given in [START_REF] Schumacher | Security Engineering with Patterns -Origins, Theoretical Models, and New Applications[END_REF], we propose the following: Definition 1 (Security and Dependability Pattern). A security and dependability pattern describes a particular recurring security/and or dependability problem that arises in specific contexts and presents a well-proven generic scheme for its solution.

Unfortunately, most of S&D patterns are expressed, as informal indications on how to solve some security problems, using identical template to traditional patterns. These patterns do not include sufficient semantic descriptions, including those of security and dependability concepts, for automated processing within a tool-supported development and to extend their use. Furthermore, due to manual pattern implementation use, the problem of incorrect implementation (the most important source of security problems) remains unsolved. For that, model driven software engineering can provide a solid basis for formulating design patterns that can incorporate security and dependability aspects and offering such patterns at several layers of abstraction. We will use metamodeling techniques for representing and reasoning about S&D patterns in model-based development. Note, however, that our proposition is based on the previous definition and on the classical GoF [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF] specification, and we deeply refined it in order to fit with the S&D needs.

To foster reuse of patterns in the development of critical systems with S&D requirements, we are building on a metamodel for representing S&D pattern in the form of a subsystem providing appropriate interfaces and targeting S&D properties to enforce the S&D system requirements. Interfaces will be used to exhibit pattern functionality in order to manage its application. In addition, interfaces supports interactions with security primitives and protocols, such as encryption, and specialization for specific underlying software and/or hardware platforms, mainly during the deployment activity. As we shall see, S&D and resource models are used as model libraries to define the S&D and resource properties of the pattern (see part B of Fig. 2).

Security and Dependability patterns are not only defined from a platform independent viewpoint (i.e. they are independent from the implementation), they are also expressed in a consistent way with domain specific models. Consequently, they will be much easier to understand and validate by application designers in a specific area. To capture this vision, we introduced the concept of domain view. Particularly an S&D pattern at domain independent level exhibits an abstract solution without specific knowledge on how the solution is implemented with regard to the application domain.

Definition 2 (Domain).

A domain is a field or a scope of knowledge or activity that is characterized by the concerns, methods, mechanisms, ... employed in the development of a system. The actual clustering into domains depends on the given group/community implementing the target methodology.

In our context, a domain represents all the knowledge including protocols, processes, methods, techniques, practices, OS, HW systems, measurement and certification related to the specific domain. With regard to the artifacts used in the system under development, we will identify the first classes of the domain to specialize such artifacts. For instance, the specification of a pattern at domain independent point of view is based on the software design constructs. The specialization of such a pattern for a domain uses a domain protocol to implement the pattern solution (see example of authorization pattern given in Sects. 4.1 and 4.2).

The objective is to reuse the domain independent model S&D patterns for several industrial application domain sectors and also let them be able to customize those domain independent patterns with their domain knowledge and/or requirements to produce their own domain specific artifacts. Thus, the 'how' to support these concepts should be captured in the specification languages.

Motivational Example: Authorization Pattern

As example of a common and widely used pattern, we choose the Authorization Pattern [START_REF] Schumacher | Security Patterns: Integrating Security and Systems Engineering[END_REF]. For instance, in a distributed environment in which users or processes make requests for data or resources, this pattern describes who is authorized to access specific resources in a system, in an environment in which we have resources whose access needs to be controlled. As depicted in the left part of Fig. 1, it indicates how to describe allowable types of accesses (authorizations) by active computational entities (subjects) to passive resources (protection objects).

However, these authorization patterns are slightly different with regard to the application domain. For instance, a system domain has its own mechanisms and means to serve the implementation of this pattern using a set of protocols ranging from RBAC (Role Based Access Control), Firewall, ACLs (Access Control Lists), Capabilities, and so on. For more breadth and depth, the reader is Fig. 1. Authorization pattern/protecting resources using capabilities referred to [START_REF] Tanenbaum | Distributed systems, principles and paradigms[END_REF]. To summarize, they are similar in their goal, but different in the implementation issues. The motivation is to handle the modeling of patterns following different abstraction levels. In the followings, we propose to use Capabilities [START_REF] Tanenbaum | Distributed systems, principles and paradigms[END_REF] to specialize the implementation of the authorization pattern. This solution is already used at hardware and operating system level to control resources.

More particular, the access rights of subjects with respect to objects are stored in an access control matrix M . Each subject is represented by a row and each object is represented by a column. An entry in such a matrix M [s, o] contains precisely the list of operations subject s is allowed to request on object o. A more efficient way to store the matrix is to distribute the matrix row-wise by giving each subject a list of capabilities it has for each object. Without such a capability for a specific object means that the subject has no access rights for that object. Then, requests for resources are intercepted and validated with the information in the capabilities. The interception and the validation are achieved by a special program usually referred to as reference monitor. For instance, whenever a subject s requests for the resource r of object o, it sends such a request passing its capability. The reference monitor will check whether it knows the subject s and if that subject is allowed to have the requested operation r, as depicted in the right part of Fig. 1. Otherwise the request fails. It remains the problem of how to protect a capability against modification by its holder. One way is to protect such a capability (or a list of them) with a signature handed out by special certification authorities named attribute certification authorities.

Pattern DSL Building Process and Artifacts

A Domain Specific Language (DSL) typically defines concepts and rules of the domain using a metamodel for the abstract syntax, and a (graphical or textual) concrete syntax that resembles the way the domain tasks usually are depicted. As we shall see, such a process reuses a lot of practices from Model-Driven Engineering (MDE), for instance, metamodeling and transformation techniques. There are several DSML (Domain Specific Modeling Language) environments available. In our context, we use the Eclipse Modeling Framework (EMF) [START_REF] Steinberg | EMF: Eclipse Modeling Framework 2.0[END_REF] open-source platform. Note, however, that our vision is not limited to the EMF platform.

In Fig. 2, we illustrate the usage of a DSL process based on MDE technology to define the modeling framework to design a pattern on one hand and the use of such a framework on the other hand. As shown in part A of Fig. 2, a DSL process is divided into several kinds of activities: DSL definition, transformation, coherency and relationships rules, designing with DSLs and qualification. The first three activities are achieved by the DSL designer and last two are used by the DSL end-user. In the following we detail the following artifacts and their related processes:

-Pattern Metamodel: Sect. 3 (see part A of Fig. 2). -Pattern Modeling. Section 4 (see part A of Fig. 2). -Pattern Formalization. Section 5 (see part C of Fig. 2). The System and Software Engineering Pattern Metamodel (SEPM), as depicted in Fig. 3, is a metamodel which defines a new formalism for describing patterns and which constitutes the base of our pattern modeling language. Such a formalism describes all the concepts (and their relations) required to capture all the facets of patterns. These patterns are specified by means of a domainindependent generic representation and a domain-specific representation.

The principal classes of the metamodel are described with Ecore notations in Fig. 3 and their meanings are more detailed in the following paragraph.

-This block represents a modular part of a system that encapsulates a solution of a recurrent problem. A DIPattern defines its behavior in terms of provided and required interfaces. Larger pieces of a system's functionality may be assembled by reusing patterns as parts in an encompassing pattern or assembly of patterns, and wiring together their required and provided interfaces. A DIPattern may be manifested by one or more artifacts. This is the key entry artifact to model patterns at domain independent level (DIPM). -Interface. A DIPattern interacts with its environment with Interfaces which are composed of Operations. A DIPattern owns provided and required interfaces. A provided interface is implemented by the DIPattern and highlights the services exposed to the environment. A required interface corresponds -Property. Is a particular characteristic of a pattern related to the concern it is dealing with and dedicated to capture its intent in a certain way. Each property of a pattern will be validated at the time of the pattern validating process and the assumptions used, will be compiled as a set of constraints which will have to be satisfied by the domain application. -Constraint. Is a requisite of the pattern. If the constraints are not met, the pattern will not be able to deliver its properties. -InternalStructure. Constitutes the implementation of the solution proposed by the pattern. Thus the InternalStructure can be considered as a white box which exposes the details of the IPatterns. In order to capture all the key elements of the solution, the InternalStructure is composed of two kinds of Structure: static and dynamic. Please, note that the same pattern could have several possible implementations -DSPattern. Is a refinement of a DIPattern. It is used to build a pattern at DSPM. Furthermore a DSPattern has TechnicalInterfaces in order to interact with the platform. This is the key entry artifact to model pattern at domain specific level (DSPM).

Generic Property Modeling Language (GPRM)

The metamodel of property [START_REF] Ziani | Towards a unified meta-model for resourcesconstrained embedded systems[END_REF] captures the common concepts of the two main concerns of trusted RCES (Resources-Constrained Embedded Systems) applications: Security, Dependability and Resource on the one hand and Constraints on these properties on the other hand. The libraries of properties and constraints includes units, types, categories and operators. For example, security attributes such as authenticity, confidentiality and availability [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF] are categories of S&D properties. The reader is referred to [START_REF] Ziani | Towards a unified meta-model for resourcesconstrained embedded systems[END_REF] for a full description of the properties metamodel. These models are used as external model libraries to type the properties of patterns. Especially during the design and later on for the selection of the pattern (see next sections), we define the properties and the constraints using these libraries. Note, however, that modeling languages such as MARTE (Modeling and Analysis of Real-Time and Embedded systems) [START_REF] Omg | A UML profile for MARTE: modeling and analysis of real-time embedded systems, beta 2[END_REF] may be used as well for depicting these properties.

Pattern Modeling Process

We now present an overview of our pattern modeling process. Along this description, we will give the main keys to understand why our process is based on a general and a constructive approach. It consists of the following phases: (1) the specification of the pattern at domain independent level (DIPM), ( 2) the refinement of DIPM pattern to specify one of its representations at domain specific level (DSPM). These two levels of the Authorization pattern presented in Sect. 2.2 are illustrated. For the sake of simplicity, many functions and artifacts of this pattern have been omitted. We only detail the properties and interfaces that we need to describe the validation process. Note that the document representing the formalization and the proof are detailed in Sect. 5.

Domain Independent Pattern Model (DIPM)

This level is intended to generically represent patterns independently from the application domain. This is an instance of the SEPM. As we shall see, we introduce new concepts through instantiation of existing concepts of the SEPM metamodel in order to cover most existing patterns in safety critical applications. In our example, the DIPM of the authorization pattern consists of:

-Properties. At this level, we identify one property: confidentiality.

-External Interfaces. The authorization pattern exposes its functionalities through function calls:

req(S, AT, P R): the subject S sends request about access type AT concerning the protected resource or data P R.

Domain Specific Pattern Model (DSPM)

The objective of the specific design level is to specify the patterns for a specific application domain. This level offers artifacts at down level of abstraction with more precise information and constraints about the target domain. This modeling level is a refinement of the DIPM, where the specific characteristics and dependencies of the application domain are considered. Different DSPM would refine a same DIPM for all needed domain. For instance, when using Capabilities as a mechanism related to the application domain to refine the authorization pattern at DSPM, we identify the following artifacts:

-Properties. In addition to the refinement of the property of confidentiality identified in the DIPM, at this level, one can consider: deny unauthorized access, permit authorized access, and efficiency properties. -External Interfaces. This is a refinement of the DIPM external interface: req(S, AT, P R, C): the subject S sends request about access type AT concerning the protected resource P R passing its capability C. -Technical Interfaces. Let the subset of functions related to the use of capabilities to refine the authorization pattern:

sign(C): the certification authority signs the capability C, verif yCert(): the attribute capability certificate is verified, -extractCap(): the capability is extracted from the certificate, -checkRight(S, AT, P R, C): the reference monitor verifies, using the capability, whether P R appears in the C.

Pattern Validation Process

We propose to use theorem proving techniques to formalize patterns and to prove their properties. This part completes the framework as depicted in Fig. 2 (see Part C ). In our work, we used the interactive Isabelle/HOL proof assistant [START_REF] Nipkow | Isabelle/HOL -A Proof Assistant for Higher-Order Logic[END_REF] to do so. First we model the pattern as a data type. Then we define and prove a set of properties and constraints that it meets. These two steps are applied successively to DIPM and DSPM levels. Finally, we deal with the correspondence between the DIPM and DSPM formal models.

Pattern Formalization

Before coding the pattern and its properties in Isabelle/HOL, one has to define what are an agent and an action. Both are records i.e. tuples, with a name attached to each component. We note i action the record for an action defined at the DIPM level, and we will talk about s action when dealing with the specific level. The right part of the action data type with "..." refers to specific actions defined at the DSPM model. Definitions mainly concern the refinement process of pattern from the DIPM model to the DSPM model. We formalize this refinement by adding to the definitions of DIPM a subset of functions related to the mechanisms employed in the application domain. Compared to independent actions embodied by the i action records at the DIPM level of the pattern, records of type s action devoted to DSPM may have additional fields. This is easily done by the s action definition of which extends the first specification by the keyword + (see left part of Table 1). We so consider that the DSPM formal model contains the same set record s action = i action + data : : "dataType" capability : : "capabilityType" record agent = name : : "agentType" i actions : : "i action set" s actions : : "s action set" of agents as the DIPM one. Its actions correspond to the external and internal domain specific interface function calls.

For our case, we introduce how to specify the confidentiality property. Let G be a set of agents, D be the critical data and A be the actual set of actions that use D. Then, the confidentiality property on D, denoted by conf (A, D, G), means that only agents in G are allowed to know the value of D. All others, when looking at actions in A shall not be able to derive its value.

The definitions and the proofs used in this section are extracted from the code of our experiment applied to the authorization pattern and its related mechanism from the application domain: capabilities. Table 1 defines these artifacts in Isabelle.

Domain Independent Pattern Model (DIPM).

As previously defined in Sect. 4.1, the authorization pattern exposes its functionalities through the function calls req(S, AT, P R). In this formula, the subject S sends requests about access type AT concerning the protected data P R. Applying the previous definition conf, we get A = req(S, at, P R) where at ∈ AT, D = P R and G = S.

Function calls req(S, at, P R) are independent requests of the authorization pattern formalized in Isabelle as shown in the left part of Table 2 owing to the create i Action definition and the req constant. In the same way, an agent is introduced by the createAgent definition and the subject constant nominates the active computational entity of the pattern.

Domain Specific Pattern Model (DSPM).

The DSPM model of the authorization pattern introduces a capability C as mechanism to ensure the communication between the subject and the passive resources. Consequently, the DSPM req(S, AT, P R, C) external interface is a refinement of the DIPM one where the subject S sends requests about access type AT concerning the protected resource P R passing its capability C. We formalize this refinement by the code in the right part of Table 1 which adds to the definitions of the DIPM part the subset of functions sign, verif yCert, extractCap and checkRight related to capabilities. This code also defines the counterpart s action of an independent action i action. For sake of clarity, we only give the code of the checkRight constant defined as an s action.

Following the definition of Sect. 4.1 and applying the previous definition conf, we get the confidentiality property conf (checkRight(S, at, P R, C), P R, S).

Pattern Validation

The goal now is to identify the set of assumptions required to prove the properties. Then, the proof consists to find a scheduling of valid steps using Isabelle's tactics such as applying (command apply) a simplification considering that each step corresponds to a sub-goal to resolve. Our proof only uses simplification rules (command simp) which consist in rewriting specified equations from left to right in the current goal. Correctness of the proof is guaranteed by construction from the first goal to resolve (a lemma or a theorem) until the message "no subgoals" is produced by the framework which confirms that the proof is finished (command done).

Domain Independent Pattern Model (DIPM).

For our case, we have to find the assumptions for the conf (req(S, at, P R), P R, G) property to hold, supposing S ∈ G and at ∈ AT. Informally, to achieve such a property, we need to demonstrate that G is the only set of agents that can access to P R using an action req(S, at, P R) and that such an action doesn't provide any information to an agent outside of G in order to derive the value of the protected data. The pattern describes in fact who is authorized to access specific resources in a system and whose accesses need to be controlled.

By definition, as presented in Sect. 2.2, we have a vector M [s1.

.sn][P R] to denote the access rights. An entry in such a matrix M [si, P R] contains precisely the list of operations of AT subject si that are allowed to request on the object P R. At this level, it's obvious that the only agents allowed to use the protected data are those listed in the defined matrix. For the second concern, we have to assume that the matrix is protected itself and that agents outside of G looking at actions in req(S, at, P R) shall not be able to derive the value of P R. In our Isabelle experiment, we have weakened these constraints assuming two predicates isAllowed for authorized accesses to a specific resource and isP rotected related to its encapsulated access. We simulate the matrix by a set of actions. We also ensure that the term req(S, at, P R) verifies these preconditions. With these assumptions, the relation conf (req(S, at, P R), P R, S) holds as proved by the lemma confReq (confidentiality of the req request) of the left part of Table 3.

In the next section, using a specific mechanism, namely Capabilities, to implement such a pattern, we will refine these assumptions.

Domain Specific Pattern Model (DSPM).

As an example, the confidentiality property conf (checkRight(S, at, P R, C), P R, S) is then established by the conf CheckRight lemma (confidentiality of the checkRight request) given in the right part of Table 3, with similar simplification tactics when proving the conf Req lemma of the left part of Table 3.

For our experiment, no assumptions have been introduced for this proof, but we can easily extend our formalization by considering for instance a precedence order between the calls sign, verif yCert, extractCap and checkRight related to capabilities.

Correspondence between DIPM and DSPM

Correspondence between the DIPM and DSPM formal models is assumed when proving that the property introduced at the DIPM model is transferred to the DSPM model. More precisely, this means that the DIPM model is an abstraction of the DSPM model. In particular, we must show that using a specific mechanism for verifying the property together with function calls of the specific domain is a specific case of proving the upper-level property.

We so have to map actions of the DSPM model onto the actions of the DIPM model by an appropriate homomorphism h and then prove that this homomorphism preserves the property. As a property is proved both for the DIPM and DSPM models, h validates the refinement of the proof. In practice, h is required to preserve each operation or a pseudo-operation which summarizes the behavior of a set of operations.

In our case, we must show that using capabilities for verifying the property conf (checkRight(S, at, P R, C), P R, S) together with function calls of the specific domain is a specific case of proving the upper-level property conf (req(S, at, P R), P R, S). Fig. 4 specifies h and the resulting conf ReqH theorem (confidentiality of the req request using h). In this code, for simplicity of illustration, we only map checkRight to req, and we introduce a null action for all other mappings.

Hence h preserves confidentiality into the DIPM request access to the protected data. The conf (req(S, at, P R), P R, S) relation transferred to the DSPM model is identical to conf (checkRight(S, at, P R, C), P R, S). We can formally verify this assumption according to the Isabelle's framework which displays the same sub-goals to resolve as soon as the DSPM current goal of Fig. 4 has been split by a case distinction on a Boolean condition (command simp with if def ). Design patterns are a solution model to generic design problems, applicable in specific contexts. Supporting research tackles the presented challenges includes domain patterns, pattern languages and recently formalisms and modeling languages to foster their application in practice. To give an idea of the improvement achievable by using specific languages for the specification of patterns, we look at pattern formalization and modeling problems targeting the integration of the pattern specification and validation steps into a broader MDE process.

Several tentatives exist in the literature to deal with patterns for specific concern [START_REF] Di Giacomo | Using security and dependability patterns for reaction processes[END_REF][START_REF] Yoshioka | A survey of security patterns[END_REF]. They allow to solve very general problems that appear frequently as sub-tasks in the design of systems with security and dependability requirements. These elementary tasks include secure communication, fault tolerance, etc. The pattern specification consists of a service-based architectural design and deployment restrictions in form of UML deployment diagrams for the different architectural services.

To give a overview of the improvement achievable by using specific languages, we look at the pattern specification and formalization problems. UMLAUT [START_REF] Guennec | Precise modeling of design patterns[END_REF] is an approach that aims to formally model design patterns by proposing extensions to the UML metamodel 1.3. They used OCL language to describe constraints (structural and behavioral) in the form of meta-collaboration diagrams. In the same way, RBML(Role-Based Metamodeling Language) [START_REF] Kim | A UML-based metamodeling language to specify design patterns[END_REF] is able to capture various design perspectives of patterns such as static structure, interactions, and state-based behavior.

While many patterns for specific concern have been designed, still few works propose general techniques for patterns. For the first kind of approaches [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF], design patterns are usually represented by diagrams with notations such as UML object, annotated with textual descriptions and examples of code. There are some well-proven approaches [START_REF] Douglass | Real-time UML: Developing Efficient Objects for Embedded Systems[END_REF] based on Gamma et al. However, this kind of technique does not allow to reach the high degree of pattern structure flexibility which is required to reach our target.

Formal specification has also been introduced in [START_REF] Mikkonen | Formalizing design patterns[END_REF] in order to give rigorous reasoning of behavioral features of a design pattern in terms of high-level abstractions of communication. In this paper, the author considers an objectoriented formalism for reactive system (DisCo) [START_REF] Jarvinen | Disco specification language: marriage of actions and objects[END_REF] based on TLA (Temporal Logic of Actions) to express high-level abstractions of cooperation between objects involved in a design pattern. However, patterns are directly formalized at the pattern level including its classes, its relations and its actions, without defining a metamodel.

[6] presents a formal and visual language for specifying design patterns called LePUS. It defines a pattern in an accurate and complete form of formula in Z, with a graphical representation. With regard to the integration of patterns in software systems, the DPML (Design Pattern Modeling Language) [START_REF] Mapelsden | Design pattern modelling and instantiation using dpml[END_REF] allows the incorporation of patterns in UML class models. However, this kind of techniques does not allow to achieve the high degree of pattern structure flexibility which is required to reach our target, and offered by the proposed pattern modeling language. The framework promoted by LePUS is interesting but the degree of expressiveness proposed to design a pattern is too restrictive.

Regarding the analysis aspects, [START_REF] Hatebur | A security engineering process based on patterns[END_REF] used the concept of security problem frames as analysis patterns for security problems and associated solution approaches. They are also grouped in a pattern system with a list of their dependencies. The analysis activities using these patterns are described with a highlight of how the solution may be set, with a focus on the privacy requirement anonymity. For software architecture, [START_REF] Halkidis | A qualitative analysis of software security patterns[END_REF] presented an evaluation of security patterns in the context of secure software architectures. The evaluation is based on the existing methods for secure software development, such as guidelines as well as on threat categories.

Another important issue is the identification of security patterns. [START_REF] Cheng | Using security patterns to model and analyze security[END_REF] proposed a new specification template inspired on secure system development needs. The template is augmented with UML notations for the solution and with formal artifacts for the requirement properties. Recently [START_REF] Fernandez | Using security patterns to develop secure systems[END_REF] presented an overview and new directions on how security patterns are used in the whole aspects of software systems from domain analysis to the infrastructures.

To summarize, in software engineering, design patterns are considered effective tools for the reuse of specific knowledge. However, a gap between the development of systems using patterns and the pattern information still exists. This becomes even more visible when dealing with specific concerns namely security and dependability for several application sectors.

-From the pattern methodological point of view: The techniques presented above do not allow to reach the high degree of pattern structure flexibility. The framework promoted by LePUS is interesting but the degree of expressiveness proposed to design a pattern is too restrictive. The main critic of these modeling languages is that no variability support of the pattern specification, because a pattern by nature covers not only one solution, but describes a set of solutions for a recurring design problem. Furthermore there are no elements in existing modeling languages to model appropriate architectural concepts and properties provided by patterns and even more security and dependability aspects. The problem is obvious in UML and ADLs. The main shortcoming of the UML collaboration approach stems from the non-support of variability. However, we do believe that the advantages of using UML for engineering software outweigh these disadvantages. -From the pattern-based software engineering methodological point of view:

Few works are devoted to this concern. They are in line for the promotion of the use of patterns in each system/software development stage. However, existing approaches using patterns often target one stage of development (architecture, design or implementation) due to the lack of formalisms ensuring both (1) the specification of these artifacts at different levels of abstraction, (2) the specification of relationships that govern their interactions and complementarity and (3) the specification of the relationship between patterns and other artifacts manipulated during the development lifecycle and those related to the assessment of critical systems. -From the pattern validation process point of view: There are mainly two approaches when dealing with formal reasoning: model-checking and interactive theorem proving. Model-checking is attractive because it offers a high degree of automation and is therefore accessible to uninitiated users. However, model checkers have to provide an intuitive operational understanding of a model under properties they have to verify. In contrast theorem proving focuses on abstract properties on a model and not on its behavior. This is the case for our pattern validation process with Isabelle/HOL: proof obligations introduce formulas that are so many assumptions to validate, and DSPM actions mapped on to DIPM actions must normally encompass the same subset of proof obligations. -From the tool support point of view: Existing tools support the specification of patterns and their application in the design of software systems, notably Netbeans, StarUML, Sparx systems. In these tools, patterns are provided as UML libraries and usually embedded in the tool without extension support. The integration of pattern in these tools result merely in copying a solution into a model.

Conclusion and Future Work

We present an approach for the design and verification of patterns to provide practical solutions to meet security and dependability (S&D) requirements. As it follows the MDE paradigm for system's design, using patterns on different levels of abstraction, it allows for integration into the system's design process, hence supports this process. To this end, the proposed representation takes into account the simplification and the enhancement of such activities, namely : selection/search based on the properties, and integration based on interfaces. Yet the system development process is not the topic we focus on in our paper.

Indeed, a classical form of pattern is not sufficient to tame the complexity of safety critical systems -complexity occurs because of both the concerns and the domain management. To reach this objective and to foster reuse, we introduced the specification at domain independent and domain specific levels. The former exhibits an abstract solution without specific knowledge on how the solution is implemented with regard to the application domain. Following the MDE process, the domain independent model of patterns is then refined towards a domain specific level, taking into account domain artifacts, concrete elements such as mechanisms to use, devices that are available, etc.

We also provide an accompanying formalization and validation framework to help precise specification of patterns based on the interactive Isabelle/HOL proof assistant. The resulting validation artefacts may mainly (1) complete the definitions, and (2) provide semantics for the interfaces and the properties in the context of S&D. Like this, validation artefacts may be added to the pattern for traceability concerns. In the same way, the domain refinement is applied during the formal validation process for the specification and validation of patterns.

Furthermore, we walk through a prototype of EMF tree-based editors supporting the approach. Currently the tool suite named Semcomdt1 is provided as Eclipse plugins. The approach presented here has been evaluated on two case studies from TERESA's project2 resulting in the development of a repository of S&D patterns with more than 30 S&D patterns. By this illustration, we can validate the feasibility and effectiveness of the proposed specification and design framework.

The next step of this work consists in implementing other patterns including those for security, safety, reconfiguration and dependability to build a repository of multi-concerns patterns. Another objective for the near future is to provide guidelines and tool-chain supporting the whole pattern life cycle (i.e., create, store patterns, retrieve) and the integration of pattern in an application. All patterns are stored in a repository. Thanks to this, it is possible to find a pattern regarding to concern criteria. At last, guidelines will be provided during the pattern development and the application development (i.e., help to choose the appropriate pattern and its usage).

Fig. 2 .

 2 Fig. 2. Overview of the pattern DSL building process and artifacts

Fig. 3 .

 3 Fig. 3. The SEPM metamodel-overview

  datatype actionType = req | ... datatype accessType = at datatype dataType = PR datatype capabilityType = C record i action = datatype actionType = req | ... | checkRight agent : : "agentType" access : : "accessType"

Fig. 4 .

 4 Fig. 4. Proving the correspondence between DIPM and DPSM models

Table 1 .

 1 Data types for the authorization pattern

Table 2 .

 2 Definitions of the authorization pattern

	DIPM	DSPM
	definition create i Action : :
	"agentType ==> accessType ==> dataType
	==> i action"
	where
	"create i Action ag a d == (agent=ag,	definition create s Action : :
	access=a, data=d)"	"agentType ==> accessType
		==> dataType ==> capabilityType
	definition req : : "i action" where	==> s action" where
	"req == create i Action S at PR"	"create s Action ag a d c ==
		(agent=ag, access=a, data=d,
	definition createAgent : :	capability=c)"
	"agentType ==> (i action set)
	==> (s action set) ==> agent"	definition checkRight : : "s action"
	where	where
	"createAgent ag i as s as ==	"checkRight == create s Action S
	(name=ag, i actions=i as, s actions=s as)" at PR C"
	definition subject : : "agent" where
	"subject == createAgent S req
	checkRight, ..."

Table 3 .

 3 Proving the conf property

	DIPM

http://www.semcomdt.org

http://www.teresa-project.org/