Sam Azimi
email: azimi@univ-paris12.fr

Vincent Rocher

Re ´gis Mathieu Muller

Daniel R Moilleron

Thevenot
email: thevenot@univ-paris12.fr

Sources, distribution and variability of hydrocarbons and metals in atmospheric deposition in an urban area (Paris, France)

Keywords: Aliphatic hydrocarbon, PAH, Heavy metal, Fingerprint, Origin

Total atmospheric deposition, i.e., both wet and dry deposition, was sampled during 11 months in the bIle-de-FranceQ region, France. Monthly fluxes of aliphatic hydrocarbons (AHs), polycyclic aromatic hydrocarbons (PAHs) and heavy metals (HMs) were studied at three representative sites (two urbanised and one semiurban). A combination of spatial and temporal variability of total fluxes and pollutant fingerprints allows a better understanding of atmospheric pollutant dynamics over this region. In the whole studied area, aggregated total atmospheric fluxes of AHs, PAHs and HMs range from 19 to 33 mg m À2 y À1 , 99 to 161 Ag m À2 y À1 and 48 to 103 mg m À2 y À1 , respectively. The highest values are observed in Paris centre, reflecting the importance of the urban centre as a source of pollutants, with a decline in many atmospheric deposits when moving away from urban areas. The seasonal distribution of these pollutants suggests the impact of residential heating on urban atmospheric deposition of hydrocarbons and the increase of dust loads containing HMs during summer. The qualitative study performed on atmospheric deposition data highlights the main sources of pollutants. Aliphatic fingerprints suggest a marked contribution of biogenic inputs to aliphatic contamination in the whole Ile-de-France region and slight petroleum inputs in urban areas. Aromatic fingerprints, characterised by the great predominance of phenanthrene, fluoranthene and pyrene, associated with some specific ratio values, suggest the mixture of petrogenic and pyrolytic contaminations of atmospheric deposition in the whole bIle-de-FranceQ region. HM distribution shows the presence of anthropogenic sources of Al and Fe in this area and the stationary sources (incinerators and plants) as a significant source of Si, S and Sb in the urban atmosphere. Moreover, a pollutant mix phenomenon, occurring in such an urban atmosphere, shows a significant influence on atmospheric deposition at the semiurban site.

Introduction

Atmospheric pollutants such as aliphatic hydrocarbons (AHs), polycyclic aromatic hydrocarbons 0048-9697/$ -see front matter D 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.scitotenv.2004.06.020 (PAHs) and heavy metals (HMs) have long been recognised as potential threats to the environment and human health. During the past decades, government efforts to control air pollution have achieved some positive effects, and as a result, atmospheric pollutants have been reduced significantly. In many locations, evidence of the decline in pollutant concentrations has been reported [START_REF] Azimi | Trace metal determination in total atmospheric deposition in rural and urban areas[END_REF][START_REF] Cortes | Temporal trends in and influence of wind on PAH concentrations measured near the Great Lakes[END_REF]. However, air pollution is still a major problem and tighter emission controls are being enforced by many governments. The urban atmosphere is subjected to large inputs of anthropogenic contaminants produced by both stationary (power plants, industries and residential heating) and diffuse sources (road traffic; [START_REF] Bilos | Sources, distribution and variability of airborne trace metals in La Plata City area, Argentina[END_REF][START_REF] Schauer | Source apportionment of airborne particulate matter using organic compounds as tracers[END_REF]. According to their different physical and chemical properties (vapor pressure, Henry's law constant), the size and composition of the source particles, these pollutants are partitioned between particulate and vapor phases and are subsequently transported to the Earth's surface through dry and wet deposition [START_REF] Lawlor | Metals in bulk deposition and surface water at two upland locations in northern England[END_REF]. From a biogeochemical perspective, the characterisation of total atmospheric deposition is relevant in order to identify the variability and sources of the atmospheric pollutants.

Generally, studies performed on these kinds of pollutants, as PAHs or HMs, determine fluxes at only one site and compare their results with those from other work done in the same areas [START_REF] Maneux | Temporal patterns of the wet deposition of Z, Cu, Ni, Cd and Pb: the Arcachon lagoon (France)[END_REF][START_REF] Ollivon | Atmospheric deposition of PAHs to an urban site, Paris, France[END_REF]. Such approaches allow an estimation of pollutant spatial variations but may induce much bias because the sampling and analysis techniques are not standardised from one study to another. In this present research program, we measured the hydrocarbon (both the particulate and the soluble fractions of the aliphatic and aromatic com-pounds) and the HM (the acid-soluble fraction) pollution in monthly bulk atmospheric deposition, i.e., dry and wet deposition sampled together. These deposits were sampled over 11 months at three stations situated in a residential area (Paris centre), an industrial suburb sector (Cre ´teil) and a semiurban sector of this region (Coulommiers). The first aim of this work is to determine atmospheric fallout fluxes in order to assess their spatial variability in this area and to estimate their seasonal changes. Secondly, pollutant fingerprints are investigated, using specific ratios, in order to assess their spatial and temporal variability and to elucidate the origin of atmospherically deposited pollutants.

Material and methods

Sites

This research was performed in the bIle-de-FranceQ region. This region, which includes Paris City, is the most industrialised and densely populated region of France (11 million inhabitants). It comprises many waste incinerators, power plants, various industrial plants, and especially, heavy road traffic. In order to evaluate the impact of these pollutant sources, three sampling stations were established in a 60-km long NW-SE transect through this region (Fig. 1). The first site, situated in the fourth district of Paris City (PAR, 48852VN, 2822VE), was placed on a building flat roof at 18-m height above ground level. Two potential sources may mainly affect the atmospheric deposition there: heavy urban traffic and residential heating. The second site, situated at Cre ´teil (CRE, 48847VN, 2828VE), was placed on the roof of the Paris XII University building at 20-m height above ground level. This area is much industrialised and presents many anthropogenic activities. Indeed, in addition to a heavy traffic highway (A86, 200 m, West, 60,000 vehicles/day), this site is near a power plant (1900 m, West), two waste incinerators (5700 m, North-West; 500 m, South) and an international airport (Orly, 8400 m, South-West). The third site, situated 50 km away from Paris near the town of Coulommiers (COU, 48849VN, 3805VE), was placed on grassland near agricultural fields. This area, which is far from the main anthropogenic sources, is situated under the plume of the whole urbanised area because the wind mainly blows from the west in this region (Garban et al., 2002;[START_REF] Garnaud | Caracte ´risation des retombe ´es atmosphe ´riques de me ´taux traces en milieu urbain[END_REF] and is defined as a semiurban site.

Sampling procedures

Hydrocarbons

Bulk atmospheric deposition (wet and dry) was sampled from December 2001 to October 2002 using pyramid-shaped funnels (55Â55Â70 cm) made of stainless steel. These devices collected both dry deposition and precipitation continuously for 6-week periods. The deposits were collected in 25-l aluminium bottles placed in isothermal boxes made of expanded polystyrene so as to minimise temperature variation and evaporation [START_REF] Ollivon | Atmospheric deposition of PAHs to an urban site, Paris, France[END_REF]. The whole equipment reached a height of 150 cm. At the end of each sampling period, the funnels were rinsed with 500 ml of purified water (Milli-Ro 5 Plus, Millipore) in order to release most sorbed particles from the funnel walls. The AHs and PAHs were determined separately in both particulate and dissolved fractions of each sample.

Heavy metals

The bulk deposition collectors for HMs consisted of Teflon funnels of collection area of 113 cm 2 connected to polyethylene bottles (5 l). This equipment was placed inside PVC pipes at a height of 190 cm. The sampling period of the total atmospheric deposition was 28 days. The collection bottles were filled before each sampling period with 50 ml of 10% acidified (HNO 3 65% Suprapur, Merck) ultra pure water (18,Millipore). This water layer allowed the dissolution of most particles during the sampling period. At the end of each collection period, funnels were rinsed with 100 ml of 1% acidified Milli-Q water in order to collect particles deposited or sorbed on funnel walls, and both the funnel and the bottle were then replaced by clean ones. Such sampling procedures allowed the dissolution of the acid-soluble fraction of particles which mainly comes from anthropogenic activities [START_REF] Colin | Solubility of major species in precipitation: factors of variation[END_REF][START_REF] Desboeufs | Factors influencing aerosol solubility during cloud processes[END_REF][START_REF] Sandroni | Atmospheric deposition of metallic pollutants over the Ligurian Sea: labile and residual inputs[END_REF]. The crustal elements contained in the insoluble fraction have not been considered in this paper.

Analysis procedures

For hydrocarbons, the particulate fraction was Soxwave extracted by a CH 2 Cl 2 -MeOH mixture. The filtered fraction (b0.45 Am) was liquid-liquid extracted with CH 2 Cl 2 . After purification and separation into aliphatic and aromatic fractions, both types of subsamples were injected on a GC-MS (1800 A, Hewlett Packard). Hydrocarbons were quantified using a mixture of perdeuterated hydrocarbons added to the samples prior to extraction. For acid-soluble metal fraction, the acidified samples were filtered (b0.45 Am) and the filtrate was analysed with an ICP-AES Perkin Elmer Optima 3000. Quality control was performed using test samples. The whole analysis procedure is described in detail by [START_REF] Rocher | Biofilm in combined sewer: wet weather pollution source or/and dry weather pollution indicator?[END_REF] for hydrocarbons and by [START_REF] Azimi | Trace metal determination in total atmospheric deposition in rural and urban areas[END_REF] for metals.

Quality control procedures

Hydrocarbons

Each step of the whole procedure has been separately investigated. Laboratory blanks (LB) and field blanks (FB), consisting of a Milli-Q water solution and a prepared bottle filled with Milli-Q water solution transported to the field, respectively, were treated in the same way as samples. In addition, analytical blanks were included. Both laboratory and field blanks were generally between 5% and 10% of the concentrations in the samples.

The certified material SRM 1941a (U.S. Department of Commerce, National Institute of Standards and Technology, Gaithersburg, MD 20 899, USA), which presents certified values for aromatic hydrocarbons, was used to evaluate the Soxwave extraction efficiency. Depending upon the hydrocarbon selected, the recovery ranged between 58% and 138%. These results, quite similar to those of [START_REF] Evans | The source, composition and flux of PAH in sediments of the river Derwent, Derbyshire, UK[END_REF], i.e., 83% and 131%, have been calculated using the indicative values given by NIST. In order to evaluate the liquid-liquid extraction efficiency, we used Florida TPH mix (NSI Environmental Solutions), which is a mixture of 17 dissolved aliphatic hydrocarbons from C 10 to C 40 . The recovery was 96F15% (averageFstandard deviation).

Heavy metals

The validation procedure for heavy metal determination consists of three steps using laboratory blanks (LB), field blanks (FB) and samples certified for trace metals. LB were chosen as 1% nitric acid solution while FB consisted of 50 ml of a 1% nitric acid solution transported to the field. Both LB and FB are below the sample concentration values for all heavy metals, except for Cd and Cr, showing that material cleaning and sampling treatment procedures have no significant effect on heavy metal analysis. So, for Cd and Cr, we assumed that estimated fluxes are overestimations.

The accuracy of the analytical results was verified using two samples certified in dissolved trace. For some elements (Cd, Cu, Fe and Na), deviations between measured and certified values are less than 10%. In the case of Pb, there is a relatively high deviation between certified and measured values (54%) for low concentration samples, but this level is 10 times lower than 90% of the measured values at the Coulommiers site. For other elements, the devia-tion is between 15% and 25%, but measured concentrations are included in the uncertainty interval given for the certified values. Therefore, analytical conditions are considered as validated for atmospheric trace metal analysis.

Results and discussion

Pollutant fluxes

Hydrocarbon and metal pollutant fluxes presented in the following sections are calculated by summing pollutant fluxes collected in both the particulate and dissolved fractions for AHs and PAHs and in the acidsoluble fraction for HMs.

Spatial variability

Fig. 2 shows the annual deposition fluxes (mg m À2 y À1 ) of hydrocarbon and metal pollutants. For hydrocarbons, aliphatic and aromatic compounds are distinguished. Total AHs are the sum of more than 20 nalkanes, i.e., from n-C8 to n-C33, and two isoprenoids prystane and phytane. Total PAHs are the sum of the 16 PAHs selected from the priority list of the U.S.-EPA. For metallic pollutants, Al and Fe and trace heavy metals (THMs) are distinguished. The first group (Al and Fe) fluxes are calculated by the summation of both Al and Fe fluxes while THM fluxes are the sum of the fluxes of the 13 following elements: Ba, Cd, Co, Cr, Cu, Ni, Mn, Pb, Sb, Sr, V, Ti and Zn. For each type of pollutant (total AHs, total PAHs, Al and Fe, total THMs), annual deposition fluxes are calculated by aggregating total deposition fluxes calculated over the whole sampling period.

3.1.1.1. Total AHs. Fluxes measured at Paris, Cre ´teil and Coulommiers reach 33, 19 and 30 mg m À2 y À1 , respectively (Fig. 2). The Paris flux level is the highest among the three sites. This result underlines the impact of a densely populated area, including both residential heating and heavy road traffic, on total AH atmospheric deposition. A similar impact was observed in particulate fallout in Alexandria (Egypt; [START_REF] Aboulkassim | Aliphatic and aromatic hydrocarbons in particulate fallout of Alexandria, Egypt: sources and applications[END_REF] and in airborne particles in the La Plata area (Argentina; [START_REF] Colombo | Sources, distribution and variability of airborne particles and hydrocarbons in La Plata area, Argentina[END_REF]. The Coulommiers flux level is close to that of Paris. Nevertheless, we assume that, in contrast to the case of Paris, aliphatic hydrocarbons identified in this semiurban site do not originate from anthropogenic activities. Surprisingly, the atmospheric deposition of total AHs at the Cre ´teil site is lower than for Paris, although the sites are only 10 km apart.

Total PAHs.

The total PAH levels show quite similar values at both urban sites because the annual deposition fluxes of these pollutants reach 161 and 153 Agm À2 y À1 for Paris and Cre ´teil, respectively (Fig. 2). This deposition level appears to be within the same range as most urban areas. Indeed, [START_REF] Manoli | Chemical characterisation and source identification/apportionment of fine and coarse air particles in Thessaloniki, Greece[END_REF] reported that total PAH fluxes ranged from 73 to 401 Agm À2 y À1 , in 1997, in an urbanised site in Northern Greece. Similarly, deposition fluxes of 230 and 363 Ag m À2 y À1 were observed in Texas and Miami, respectively [START_REF] Lang | Organic aerosols in the Miami area, USA: temporal variability of atmospheric particles and wet/dry deposition[END_REF][START_REF] Park | Atmospheric distribution of poluycyclic aromatic hydrocarbons and deposition to Galveston Bay, Texas, USA[END_REF]. Therefore, total PAH deposition fluxes are similar in several urban areas of the north hemisphere. The annual deposition flux in the semiurban site (Coulommiers) is 100 Agm À2 y À1 , i.e., 40% lower at 50 km from the Paris and Cre ´teil sites. This result reflects the importance of urban areas as a source of PAHs and the decline in PAH deposition outside of urban areas.

Al and Fe.

Deposition fluxes of Al and Fe are very close at both urban sites but lower at the semiurban site (Fig. 2). Values reach 258, 291 and 107 mg m À2 y À1 at Paris, Cre ´teil and Coulommiers, respectively. Similar results were previously obtained in this urban site because [START_REF] Azimi | Trace metal determination in total atmospheric deposition in rural and urban areas[END_REF] reported a total Al and Fe flux of 234 mg m À2 y À1 at Cre ´teil during a 6-month campaign in 2000. The flux determined at the remote site is also in good agreement with the data range reported in the literature, i.e., 33 to 139 mg m À2 y À1 [START_REF] Azimi | Trace metal determination in total atmospheric deposition in rural and urban areas[END_REF][START_REF] Kim | Atmospheric wet deposition of trace elements to Chesapeake and Delaware Bays[END_REF]. Therefore, a constant atmospheric deposition flux is observed for at least a 3-year period. The relative increase of 140% between Coulommiers and Paris (170% between Coulommiers and Cre ´teil) suggests that acid-soluble Al and Fe mainly originate from anthropogenic activities. Moreover, the highest flux obtained at Cre ´teil even suggests that these elements are mainly emitted by stationary sources, i.e., waste incinerators or power plants, and not by residential heating or road traffic, which are the main sources in Paris centre.

Total THMs. Total annual heavy metal flux at

Paris centre is estimated at 103 mg m À2 y À1 . This flux is higher by a factor of 1.5 and 2 than those for Cre ´teil and Coulommiers (Fig. 2). Similar flux values have been previously reported in urban areas, ranging from 28 to 131 mg m À2 y À1 [START_REF] Golomb | Atmospheric deposition of toxic onto Massachusetts Bay: I. Metals[END_REF][START_REF] Guieu | Atmospheric inputs of dissolved and particulate metals to the northwestern Mediterranean[END_REF]. In contrast, the flux measured at the Coulommiers site is higher than fluxes previously obtained at other rural areas. For examples, values ranging from 27 to 29 mg m À2 y À1 were reported in the North Sea area (Belgium) and near the Great Lakes in the United States of America [START_REF] Injuk | Deposition of atmospheric trace element into the North Sea: coastal, ship, platform measurements and model predictions[END_REF][START_REF] Sweet | Atmospheric deposition of trace metals at three sites near the great lakes[END_REF]. Differences between the three sites (Paris, Cre ´teil and Coulommiers) are probably due to differences in their anthropogenic activities. Presumably, the high density of urban and industrial sources in Paris suburbs is responsible for the high fluxes measured at Paris, and to a lesser extent, at Cre ´teil. Moreover, it seems that the highest flux obtained at the Paris site indicates road traffic and/or residential heating as the main sources of these elements.

Seasonal variability

Fig. 3 presents seasonal variations of total AHs, total PAHs, Al and Fe and total THMs. Results obtained during 11 months are grouped by season as follows: winter period from December to early March, spring from March to June, summer from early July to September and fall from late September to early November. All quarterly fluxes are calculated for 3month periods whatever the sampling duration. In the following sections, the cold period refers to fall and winter quarters and the warm period refers to spring and summer quarters.

3.1.2.1. Total AHs. Similar seasonal trends are observed at the three sites of the Paris suburbs. Indeed, for the three sites, quarterly total AH fluxes during the cold period, which range from 5.3 to 16.1 mg m À2 q À1 , are significantly greater (99% confidence level) than those for the warm period, which range from 1.2 to 4.1 mg m À2 q À1 (Fig. 3). Differences are found to be quite important because cold period fluxes are approximately 4.5, 2.5 and 3.6 times higher than those for the warm period at Paris, Cre ´teil and Coulommiers, respectively. Such seasonal variations observed in the Paris area are in good agreement with previous studies carried out in other countries. For example, experiments performed in the metropolitan area of Miami (USA) showed that the winter flux was nearly twice as high as that of summer [START_REF] Lang | Organic aerosols in the Miami area, USA: temporal variability of atmospheric particles and wet/dry deposition[END_REF].

3.1.2.2. Total PAHs. Similar seasonal trends are observed at both urban sites. Indeed, during the warm period, total PAH fluxes range from 23 to 36 and from 28 to 39 Agm À2 q À1 at Paris and Cre ´teil, respectively, whereas cold period fluxes range from 46 to 54 and from 42 to 45 Agm À2 q À1 at the same sites (Fig. 3). A seasonal difference is observed at both sites because the cold period fluxes of total PAH are 1.5 times greater than those of the warm period. Our study confirms previous results reported for urban sites [START_REF] Halsall | Atmospheric deposition of polychlorinated dibenzo-p-dioxins/dibenzofurans and polycyclic aromatic hydrocarbons (PAHs) in two UK cities[END_REF][START_REF] Ollivon | Atmospheric deposition of PAHs to an urban site, Paris, France[END_REF]. Because the warm flux is mainly due to vehicular traffic and industrial activities and this flux is nearly steady throughout the whole year, the increase of PAH load in winter -evaluated at 41% at Paris and 22% at Cre ´teil-is attributed to residential heating in the Paris area. This result confirms data reported by [START_REF] Ollivon | Atmospheric deposition of PAHs to an urban site, Paris, France[END_REF] and [START_REF] Baek | A review of atmospheric polycyclic aromatic hydrocarbons: sources, fate and behaviour[END_REF] about the contribution of residential heating to atmospheric emissions of total PAHs estimated at: 41% in France, 36% in the USA, 26% in Sweden and 21% in Norway. The total PAH flux observed at the Coulommiers site shows no clear seasonal variation: the cold period flux ranged from 20 to 27 Agm À2 q À1 and that of the warm period from 28 to 28.5 Agm À2 q À1 . Thus, it appears that residential heating occurring at Coulommiers does not contribute significantly to hydrocarbon atmospheric deposition and the urban heating influence from Paris does not reach this semiurban site.

Al and Fe. Deposition fluxes of Al and Fe

range between 57 and 70, between 60 and 84 and between 19 and 34 mg m À2 q À1 at Paris, Cre ´teil and Coulommiers, respectively (Fig. 3). For these three sites, a slight increase in Al and Fe deposition occurs during the warm period. Indeed, the aggregated fluxes reach 110, 120 and 37 mg m À2 during the cold period and 140, 160 and 63 mg m À2 during the warm period, at Paris, Cre ´teil and Coulommiers, respectively. Increase factors during the warm period are found to be nearly similar at both urban sites (1.27 and 1.33 at Paris and Cre ´teil) and more important at the semiurban site (1.70 at Coulommiers). This increase is consistent with the observations established during 1990 at three Chesapeake Bay sites [START_REF] Scudlark | Atmospheric wet deposition of trace elements to Chesapeake Bay: CBAD study year 1 results[END_REF] and during 1994 in the North Sea area [START_REF] Injuk | Deposition of atmospheric trace element into the North Sea: coastal, ship, platform measurements and model predictions[END_REF]. Higher concentrations of elements may be attributed to the higher loads of atmospheric dusts observed during spring and summer [START_REF] Kaya | Trace element and major ion composition of wet and dry deposition in Ankara, Turkey[END_REF]. The rainfall amount and the higher surface moisture levels in fall and winter inhibit the generation of particles by resuspension of dusts.

Although such crustal particles are not totally acidsoluble, they may release Al and Fe. Therefore, the greater factor of increase observed at Coulommiers could be associated with intensity of soil disturbance related to local agricultural practices.

3.1.2.4. Total THMs. Deposition fluxes of total THM range from 17 to 26 and from 15 to 26 mg m À2 q À1 during warm and cold periods, respectively, at both urban sites (Fig. 3). THMs present a steady atmospheric quarterly flux throughout the year without any significant variation. These elements are mostly (N95%) non-crustal [START_REF] Kim | Atmospheric wet deposition of trace elements to Chesapeake and Delaware Bays[END_REF]. This result is induced by the fact that the major atmospheric sources of THMs, which are non-ferrous metal refining, waste incineration and road traffic [START_REF] Pacyna | Atmospheric emissions inventories: status and prospects[END_REF], show quite constant emission fluxes throughout the year. At the semiurban site, deposition fluxes of anthropogenic trace elements range from 10 to 16 and from 6 to 7 mg m À2 q À1 during warm and cold periods, respectively. Thus, a seasonal variation appears, characterised by maximum deposition fluxes during the warm period. Such behaviour confirms the soil disturbance at this location. Because anthropogenic activities are less important at Coulommiers, particles originating from resuspension of dust, which is an important source of many trace metals [START_REF] Sweet | Atmospheric deposition of trace metals at three sites near the great lakes[END_REF], have an important influence on atmospheric deposition.

Pollutant fingerprints

Hydrocarbon fingerprint variability

Considering that aliphatic and aromatic hydrocarbon distributions differ according to the production sources, investigation of the spatial and temporal variability of hydrocarbon fingerprints in bulk deposition allows elucidation of their origin. The aliphatic hydrocarbon indexes mainly allow the identification of biogenic and petrogenic sources, while PAH indexes are sensitive indicators of petrogenic and pyrogenic origins. In this section, spatial and temporal variability of hydrocarbon fingerprints is discussed by only taking into account the distribution of the particulate phases of bulk deposition in order to increase graphic readability. This does not induce any information loss because both particulate and dissolved phases show quite similar hydrocarbon fingerprints.

Aliphatic hydrocarbons.

As previously mentioned, n-alkanes ranging from n-C8 to n-C33 and two isoprenoids, pristane and phytane, are quantified. summer and fall periods. Aliphatic distribution patterns are found to be quite similar at all sites: the distribution pattern is bimodal, characterised by a very predominant hump peak at around n-C27/n-C29/n-C31 -n-C29 being often the major hydrocarbon (Table 1)-and a minor hump centred on n-C17/n-C18/n-C20. Predominance of heavy n-alkanes (carbon number N20) is also underlined by the light molecular weight (LMW)/high molecular weight (HMW) ratios which range from 0.04 to 0.5 (Table 1). Abundance of heavy n-alkanes and predominance of the n-C29, illustrated by n-C17/n-C29 ratios ranging from 0.03 to 0.71 (Table 1), indicate an important biogenic contamination, i.e., terrestrial plants, at both urban and rural sites [START_REF] Colombo | Determination of hydrocarbon sources using n-alcane and polyaromatic hydrocarbon distribution indexes Case study: Rio de la Plata estuary, Argentina[END_REF][START_REF] Moreda | Chromatographic determination of aliphatic hydrocarbons and polyaromatic hydrocarbons (PAHs) in a sewage sludge[END_REF]. Biogenic origins for aliphatic hydrocarbons can also be demonstrated using the odd/even n-alkane predominance. This odd/even predominance can be quantitatively formulated by different specific indexes such as the n-C16 ratio (sum of n-alkanes/n-C16) or the carbon preference index (CPI) defined as the weighted ratio of odd to even carbon-numbered n-alkanes in the n-C8-n-C33 range. The n-C16 ratio is usually large (around 50) in biogenic samples because of the dominance of odd n-alkanes and is lower (around 15) in petrogenic samples [START_REF] Colombo | Determination of hydrocarbon sources using n-alcane and polyaromatic hydrocarbon distribution indexes Case study: Rio de la Plata estuary, Argentina[END_REF]. Values of CPI near unity are typical of petrogenic origin, while greater values (i.e., above 3 to 5) indicate a biogenic origin [START_REF] Bomboi | Hydrocarbons in urban runoff: their contribution to the wastewaters[END_REF][START_REF] Bouloubassi | Investigation of anthropogenic and natural organic imputs in estuarine sediments using hydrocarbon markers (NAH, LAB, PAH)[END_REF][START_REF] Wang | Using systematic and comparative analytical data to identify the source of an unknown oil on contaminated birds[END_REF]. Table 1 shows that all bulk deposition samples are characterised by large n-alkanes/n-C16 values, i.e., in the 30-201 range, and CPI values above unity. So, odd/even predominance confirms the marked contribution of biogenic inputs to aliphatic hydrocarbon contamination in atmospheric fallout collected at both urban and semiurban sites. This latter result is in good agreement with the literature because many authors have identified biogenic materials -particularly cuticular waxes from vascular plants-as the major component of aerosols collected in urban and rural areas [START_REF] Gogou | Organic aerosols in Eastern Mediterranean: components source reconciliation by using molecular markers and atmospheric back trajectories[END_REF][START_REF] Simoneit | Molecular markers study of extractable organic matter in aerosols from urban areas of China[END_REF]. [START_REF] Colombo | Sources, distribution and variability of airborne particles and hydrocarbons in La Plata area, Argentina[END_REF] even estimated that in urban areas, plant material contributed as much as 34-96% of the airborne particulate aliphatic hydrocarbons. Nevertheless, aliphatic distributions in bulk deposition collected at both urban sites also reveal an anthropogenic aliphatic hydrocarbon contamination. Indeed, the atmospheric deposition sampled at Paris (winter and summer periods) and Cre ´teil (spring period) exhibits a relatively elevated proportion of n-alkanes from n-C15 to n-C23 (Fig. 4). The abundance of these compounds indicates that unburned lubricating oils from road traffic exhaust are a significant contributor to aliphatic hydrocarbon contamination [START_REF] Colombo | Determination of hydrocarbon sources using n-alcane and polyaromatic hydrocarbon distribution indexes Case study: Rio de la Plata estuary, Argentina[END_REF][START_REF] Simoneit | Application of molecular marker analysis to vehicular exhaust for source reconciliation[END_REF] For aliphatic hydrocarbons (AHs): MAH=major aliphatic hydrocarbon; LMW/HMW=light molecular weight (V20 carbons)/high molecular weight (N20 carbons); UCM=GC-SM unresolved complex mixture. For PAH: MPAH=major PAH; Pyr=pyrene; P=phenanthrene; Fluo=fluoranthene; LMW/HMW=light molecular weight (two-three rings)/high molecular weight (four-six rings); Alk./Par.=alkylated derivatives/parent compounds. a Alkylated derivative/parent compound ratio was assumed equal to 0 when alkylated derivative value was under the detection limit.

1985) in atmospheric deposition. In addition to resolved n-alkanes, gas chromatographic traces of aliphatic hydrocarbons are also characterised by an Unresolved Complex Mixture (UCM), i.e., the hump under the baseline on a chromatographic trace. The UCM is a complex mixture, extremely resistant to biodegradation, composed of numerous structurally complex isomers and a homologue of branched and cyclic alkanes [START_REF] Aboulkassim | Aliphatic and aromatic hydrocarbons in particulate fallout of Alexandria, Egypt: sources and applications[END_REF].

The UCM is a common feature of the gas chromatograms of crude oils and some refined products such as lubricating oils [START_REF] Colombo | Determination of hydrocarbon sources using n-alcane and polyaromatic hydrocarbon distribution indexes Case study: Rio de la Plata estuary, Argentina[END_REF][START_REF] Gough | Characterization of unresolved complex mixtures of hydrocarbons in petroleum[END_REF][START_REF] Gough | Biodegradation studies of unresolved complex mixture of hydrocarbons: model UCM hydrocarbons and aliphatic UCM[END_REF]. Therefore, the relative importance of UCM, expressed as the ratio of unresolved to resolved compounds (UCM/R), is commonly used as a diagnostic criterion for pollutant origins. In this work, depending on the seasons, UCM/R ratio values range from 2 to 10, from 2 to 7 and from 1 to 3 at Paris, Cre ´teil and Coulommiers, respectively (Table 1). These results confirm that at Paris, and to a lesser extent, at Cre ´teil, petroleum inputs contribute to the aliphatic hydrocarbon contamination of bulk deposition. On the contrary, as previously highlighted using n-alkane distributions, these petroleum inputs are negligible in the semiurban area, at Coulommiers. An evolution of the aliphatic hydrocarbon fingerprints throughout the year has also been observed at the three sites. This seasonal variability is illustrated by the fluctuation of (1) the odd carbon-numbered nalkane predominance and (2) the UCM abundance. The odd predominance is quantitatively formulated by the odd/R ratio (Fig. 5), i.e., the mass ratio of odd carbon-numbered n-alkanes to total resolved aliphatic hydrocarbons. For the three sites, the odd/R ratios display similar seasonal patterns. Values are low during the winter period-ranging from 0.46 to 0.63-reflecting the low relative contribution of biogenic sources during winter. These ratios strongly increase during spring until the values reach 0.78 to 0.88 and remain quite constant during the summer and fall periods. This trend indicates a higher relative contribution of biogenic sources during the spring, summer and fall seasons, when plants are more active. In urban areas, the relative abundance of UCM also exhibits seasonal patterns (Fig. 5). The UCM/R ratios show quite high values during the cold period and lower values during the warm period. High values obtained during winter (median values=10 and 6 at Paris and Cre ´teil, respectively; Table 1), and to a lesser extent, during fall (median values=7 and 6 at Paris and Cre ´teil, respectively; Table 1) reflect a quite strong contribution of aliphatic hydrocarbons from petrogenic sources during the cold period. Conversely, low values obtained during spring-summer seasons (median values=2-3 and 6-2 at Paris and Cre ´teil, respectively; Table 1) confirm the low contribution of petrogenic inputs compared to biogenic inputs during the warm period. of heavy PAHs (four to six aromatic rings). Indeed, except for the cases of Paris in fall and Coulommiers in spring, all LMW/HMW PAH ratios are below 0.5 (Table 1). This predominance of heavy compounds indicates a pyrolytic origin for PAH pollution because many authors have reported that the petrogenic contamination is characterised by the abundance of lower molecular weight PAHs, while higher molecular weight PAHs dominate in the pyrolytic contamination distribution [START_REF] Soclo | Origin of polycyclic aromatic hydrocarbons (PAHs) in coastal marin sediments: case studies in Cotonou (Benin) and Aquitaine (France) areas[END_REF][START_REF] Wang | Oil spill identification[END_REF][START_REF] Yang | PAH emission from various industrial stacks[END_REF][START_REF] Zheng | Characterisation of the non volatile organic compounds in the aerosols of Hong Kong: identification, abundance and origin[END_REF]. Second, phenanthrene (P), fluoranthene (Fluo) and pyrene (Pyr) are always identified as the most abundant compounds (Fig. 6). According to the seasons, their sum accounts for 76-98%, 72-92% and 71-99% of total PAHs at Paris, Cre ´teil and Coulommiers, respectively. The great predominance of these three compounds confirms the pyrolytic origin of aromatic pollutants in atmospheric deposition because they are commonly considered as typical pyrogenic products derived from high temperature condensation of lower molecular weight aromatic compounds [START_REF] Khalili | PAH fingerprints for coke ovens, diesel and gasoline engines, highway tunnels and wood combustion emissions[END_REF][START_REF] Soclo | Origin of polycyclic aromatic hydrocarbons (PAHs) in coastal marin sediments: case studies in Cotonou (Benin) and Aquitaine (France) areas[END_REF]. The impact of pyrolytic contamination is also suggested by the presence of chrysene (Chry) and benzo[a]anthracene (BaA), which are considered as markers of combustion processes [START_REF] Moreda | Chromatographic determination of aliphatic hydrocarbons and polyaromatic hydrocarbons (PAHs) in a sewage sludge[END_REF][START_REF] Soclo | Origin of polycyclic aromatic hydrocarbons (PAHs) in coastal marin sediments: case studies in Cotonou (Benin) and Aquitaine (France) areas[END_REF]. In order to distinguish between pyrolytic and petrogenic origins, the P/A and Fluo/Pyr concentration ratios can also be used. The P/A ratio is temperature-dependent with high temperature processes being characterised by low P/A values and petrogenic contamination leading to much higher P/A values. Therefore, two different categories have been defined: P/AN10 for the petrogenic sources and P/Ab10 for the dominance of pyrolytic sources [START_REF] Budzinski | Evaluation of sediment contamination by polycyclic aromatic hydrocarbons in the Gironde estuary[END_REF]. Similar considerations can be applied to the Fluo/Pyr ratio. Concerning this latter index, values above unity indicate that contamination by PAHs arises from combustion processes whereas values below unity indicate a petrogenic origin. These ratios suggest that atmospheric PAHs do not only originate from pyrolytic processes. Indeed, more than 90% of P/A and Fluo/Pyr ratio values are above 10 and below unity, respectively, underlining the impact of petrogenic sources. The presence of alkylated derivatives in both urban sites, underlined by the alkylated derivative/parent compound ratios ranging from 0.04 to 0.35 and from 0 to 0.34 at Paris and Cre ´teil, respectively, confirms the contribution of petrogenic inputs to the atmospheric pollution. Indeed, PAHs from petrogenic inputs are generally abundant in alkylated homologues relative to their parent compounds, while combustion of fossil fuels yields PAHs generally poor in alkylated homologues [START_REF] Yunker | Polycyclic aromatic hydrocarbon composition and potential sources for sediment samples from the Beaufort and Barents seas[END_REF][START_REF] Zheng | Characterisation of the non volatile organic compounds in the aerosols of Hong Kong: identification, abundance and origin[END_REF]. Finally, throughout the year, the aromatic pollution in atmospheric deposition in the whole bIle-de-FranceQ region comes from a combination of petrogenic and pyrolytic inputs. The pyrolytic origin in this region may be linked to the high density of combustion sources in the Paris suburbs. Indeed, Paris suburbs have heavy road traffic, and consequently, diesel-and gasoline-powered vehicles emit great quantities of PAHs in the environment. Besides these mobile sources, aromatic compounds are introduced in the environment through contamination by various kinds of fixed sources such as residential heating, industrial plants and industrial waste incinerators. Petrogenic contamination in atmospheric deposition may be linked to the emission of unburned lubricating oils by road traffic exhaust.

Metals fingerprint variability

3.2.2.1. Al and Fe. The distribution of Al and Fe shows that the relative amount of Fe is highest at Paris centre. Values of the Fe/Al ratio range from 1.99 to 2.10, from 1.36 to 1.82 and from 0.99 to 1.53 at Paris, Cre ´teil and Coulommiers, respectively (Table 2). Fe/ Al ratios in the Earth's crust are variable, depending on chemical enrichments. Consequently, different ratios for the upper continental crust are reported. For example, [START_REF] Wedepohl | The composition of the continental crust[END_REF] found 0.40 for the Fe/ Al ratio while [START_REF] Taylor | The geochemical evolution of the continental crust[END_REF] reported 0.84. The Fe/Al ratios measured at Paris, Cre ´teil and Coulommiers are higher than Fe/Al ratios of pure crustal sources, indicating that both elements contained in the acid-soluble fraction of particles coming from atmospheric deposition have an anthropogenic source. At the Coulommiers site, the influence of crustal particles containing Al and Fe is enhanced because the ratios obtained at this location are closer to the Earth's crustal ratio, i.e., 0.84 [START_REF] Taylor | The geochemical evolution of the continental crust[END_REF]. Concerning the seasonal variation, an increase of Fe/Al ratios appears during fall and winter at both urban sites. Such changes indicate an increase of Fe atmospheric loads probably due to the occurrence of the residential heating in winter, and to a lesser extent, in fall.

3.2.2.2. THMs. Whatever site or season is considered, the THM relative abundance has the same global pattern. Indeed, Zn is identified as the most abundant element (Fig. 7). Its relative abundance ranges from 42% to 51%, from 29% to 42% and from 38% to 50% at Paris, Cre ´teil and Coulommiers, respectively. Other main elements, for which the relative abundance ranges between 2% and 30%, decrease in the following order CuzMnNPbcBacSrNTi. The six remaining elements (Cd, Co, Cr, Ni, V and Sb) exhibit a relative abundance below 2%. The seasonal pattern of heavy metal distribution does not show a clear difference at the urbanised sites. Such an HM distribution pattern is likely to reflect the occurrence of the same sources through the year in urban areas. At the Coulommiers site, although the global pattern of the distribution does not change, the Mn and Cu relative distributions increase during the spring and summer and summer and fall periods, respectively, while the Pb relative distribution decreases during the summer period. It seems that the increase of crustal sources and agricultural activities during these periods locally influence the atmospheric deposition of Mn and Cu, respectively. The decrease of Pb can be attributed to the decrease of one of the sources of this element, e.g., road traffic [START_REF] Sternbeck | Metal emissions from road traffic and the influence of resuspension-results from two tunnel studies[END_REF][START_REF] Weckwerth | Verification of traffic emitted aerosol components in the ambiant air of Cologne (Germany)[END_REF], because the air mass trajectories did not change at this location during the whole year (the wind blew mainly from the west direction during the whole year), avoiding long-range transport influences.

To further identify common sources for pollutionderived trace elements, principal components analysis (PCA) is performed with retention of principal components (PC) having eigenvalues N1. For each site, six factors are studied and Table 3 lists element loadings and explains the variance for each factor. Loads b0.1 discarded and the significant values (N0.5) are printed in bold characters. The PCA shows that six factors are needed to explain 89%, 89% and 92% of the total variance at Paris, Cre ´teil and Coulommiers, respectively. Moreover, it appears that for several elements, two or three factors have loading values N0.1 and even N0.3, showing that, generally, trace elements have several potential sources, making the investigation of more difficult. The first factor that explains most of the variance (ranging between 36% and 39% for all sites) has high loadings for most of the elements. At the Paris location, the latter comprises elements such as Ca, Ba, Ti, Cr, Mn, Fe, Al, Pb, and to a lesser extent, K, Rb, Sr, V, Co, Ni, Cd and P. At the Cre ´teil site, the same result is obtained because the first factor has high loads for Ca, Table 3 Factor analysis on atmospheric bulk deposition fluxes dataset Sr, Ba, Mn, Fe, Co, Zn and Cd. It appears that a unique source specification for the first factor is not obvious. THMs may come from many different sources in urbanised areas, including vehicle emissions, industrial discharges and other activities. For example, Ba, Cd, Cu, Pb, Sb and Zn appear in gasoline, car components, oil lubricants, industrial and incinerator emissions [START_REF] Alloway | Heavy metals in soils: their origins[END_REF]. Thus, a mix of numerous source rejects seems to occur in the urban atmosphere because many elements are correlated to the same factor. The same result appears for the Coulommiers site, which has fewer anthropogenic sources: the first factor has high loads for many elements Rb, Mg, Ca, Sr, Ba, V, Cr, etc.). This result, associated with the wind conditions, blowing mainly from the west direction [START_REF] Garban | Atmospheric bulk deposition of PAHs onto France: trends from urban to remote sites[END_REF], shows that this location is situated under the plume of the Paris suburb activities, which have a significant influence on atmospheric deposition at this site.

With respect to other factors of the PCA, at the Paris location, high loads are found for Si, S, Li, Ag, Sn, Cr and K on factor 3. Atmospheric Si is commonly considered a crustal element, but its current association with S and Cr and the fact that only the acid-soluble fraction is analysed suggest that emissions from incinerators and coal combustion may contribute to atmospheric Si in this region [START_REF] Querol | Mobility of trace elements from coal and combustion wastes[END_REF]. At the Cre ´teil site, these sources are represented by factor 2, which has high loads in Si, S, Li, Sb, Ti, Ca and Na. At the Coulommiers site, the crustal influence of soil dust resuspension can be observed on factor 2, which has significantly high loads for Si, Al and Fe. Thus, atmospheric deposition in this area is under the influence of crustal dust resuspension as well as anthropogenic activities.

Conclusion

Atmospheric bulk deposition was sampled at three sites in the Paris area during 11 months. Collected samples were analysed for 27 aliphatic hydrocarbons, 16 aromatic hydrocarbons and 15 heavy metals using a combination of GC-SM and ICP-AES methods. Quantitative data on atmospheric pollutants show the difference in atmospheric deposition between the urban and the semiurban sites in the bIle-de-FranceQ region, France. Presumably, the high density of urban and industrial sources in the Paris suburb is responsible for the high atmospheric deposition fluxes of all measured pollutants (aliphatic hydrocarbons, PAHs and heavy metals), even elements usually considered as crustal (Al and Fe). The seasonal variability shows the increase of hydrocarbons, i.e., both aliphatic and aromatic, during fall and winter, while Al and Fe present higher deposition fluxes during spring and summer. This latter is most probably induced by the increase of atmospheric dust loads, whereas the winter hydrocarbon increase is attributed to residential heating. Trace heavy metals exhibit no significant seasonal trend because their sources are relatively constant throughout the year. The qualitative study performed on atmospheric deposition data sheds light on the main sources of these pollutants. Aliphatic fingerprints suggest a marked contribution of biogenic inputs to aliphatic contamination in the whole Paris region and slight petroleum inputs in urban areas. Whatever site or season is considered, aromatic fingerprints are characterised by a great dominance of P, Fluo and Pyr. This predominance, associated with the ratio values of P/A and Fluo/Pyr, suggests the mixture of petrogenic and pyrolytic contamination in the whole bIle-de-FranceQ region. The heavy metal source investigation appears to be more difficult than with hydrocarbons because for inorganic elements, specific ratios are less developed. However, such study underlines the presence of anthropogenic Al and Fe sources in urban areas. The PCA shows that a mix phenomenon, occurring in urban atmospheres, is propagated over the whole region according to meteorological conditions.

Fig. 1 .

 1 Fig. 1. Location of the three sampling stations established in the bIle-de-FranceQ region.

Fig. 2 .

 2 Fig. 2. Annual atmospheric deposition fluxes (mg m À2 y À1 ) of total AHs, total PAHs, Al and Fe and total THMs measured at Paris, Cre ´teil and Coulommiers.

Fig. 3 .

 3 Fig. 3. Quarterly atmospheric deposition fluxes (mg m À2 q À1 ) of total AHs, total PAHs, Al and Fe and total THMs measured at Paris, Cre ´teil and Coulommiers.

Fig. 4

 4 Fig. 4 presents the relative distribution of n-alkanes and isoprenoids in particulate atmospheric fallout collected at the three sites during the winter, spring,

  Fig. 5. Temporal variation of odd/R and UCM/R ratios (see text for ratio definition) at Paris, Cre ´teil and Coulommiers sites from December 2001 to October 2002. The number of sampling periods during each season depended on the rainfall amount of the considered seasons, which are presented by different layers (W=winter; SP=spring; S=summer; F=fall).

Fig. 6 .

 6 Fig. 6. PAH distributions in particulate atmospheric deposition collected at Paris, Cre ´teil and Coulommiers during each season.

Fig. 7 .

 7 Fig. 7. Trace heavy metal distribution in bulk deposition collected at Paris, Cre ´teil and Coulommiers during each season.

Table 1

 1 Values of alkane and PAH indexes obtained for Paris, Cre ´teil and Coulommiers sites during each season

			Paris				Cre ´teil				Coulommiers
			Winter Spring Summer Fall	Winter Spring Summer Fall	Winter Spring Summer Fall
	AHs	MAH	C29	C29	C29	C29 C29	C29	C29	C27 C29	C27	C31	C27
		LMW/HMW	0.48	0.05	0.45	0.09 0.12	0.50	0.14	0.10 0.20	0.19	0.10	0.04
		UCM/R	10	2	3	7	6	2	5	6	1	2	3	2
		CPI	1.30	2.19	3.31	3.46 1.38	2.52	4.46	3.67 1.21	5.60	7.23	8.10
		Odd/R	0.54	0.68	0.73	0.77 0.57	0.69	0.81	0.78 0.54	0.84	0.87	0.89
		Prist/phyt	0.70	0.98	1.10	1.64 0.80	0.99	0.85	0.83 1.01	0.96	1.53	1.29
		C18/phyt	1.78	2.21	2.02	2.42 1.98	1.89	2.12	1.75 1.74	2.06	2.13	2.42
		n-alkanes/C16 38	443	28	166	168	43	109	208	89	114	156	577
		C17/C29	0.40	0.03	0.40	0.05 0.08	0.71	0.17	0.08 0.12	0.14	0.06	0.04
	PAHs MPAH	Pyr	Pyr	Pyr	P	Pyr	Pyr	Pyr	Pyr	Fluo	Pyr	Fluo	Fluo
		LMW/HMW	0.48	0.20	0.45	1.04 0.51	0.30	0.52	0.23 0.42	1.06	0.44	0.04
		Alk./Par.	0.35	0.05	0.11	0.04 0.34	0.08	0.15	0 a	0 a	0 a	0.03	0 a

S.Azimi et al. / Science of the Total Environment 337 (2005) 223-239

Acknowledgements

Authors are grateful to J.-L. Colin, E. Bon and M. Lachaud for their scientific support. This work was financially supported by the PIREN-Seine Research Program (CNRS GDR 1067). The cooperation of P. Ansart (Cemagref) and the headmistress of the Ste Genevie `ve school (Paris) is fully acknowledged.

Paris

Cre ´teil Coulommiers


Chan Ngo

Jean-Pierre Talpin

Thierry Gautier

Van Chan Ngo

Precise deadlock detection for polychronous data-flow specifications

Keywords: Deadlock detection, compilation, polychrony, dependency graphs, SMT solving, formal verification

Dependency graphs are a commonly used data structure to encode the streams of values in data-flow programs and play a central role in scheduling instructions during automated code generation from such specifications. In this work, we propose a precise and effective method that combines a structure of dependency graph and first order logic formulas to check whether multi-clocked data-flow specifications are deadlock free before generating code from them. We represent the flow of values in the source programs by means of a dependency graph and attach first-order logic formulas to condition these dependencies. We use an SMT solver to effectively reason about the implied formulas and check deadlock freedom.

I. INTRODUCTION

The synchronous languages such as Esterel [START_REF] Berry | The Foundations of Esterel[END_REF], Lustre [START_REF] Halbwachs | A Synchronous Language at Work: The Story of Lustre[END_REF] and Signal [START_REF] Gamatié | Designing Embedded Systems with The Signal Programming Language: Synchronous, Reactive Specification[END_REF] have been successfully used to design safetycritical real-time systems. Synchronous programming provides a precise semantics of programs, and the system properties can be proved mathematically by using formal methods. For instance, the SCADE tool is used by European industry to develop the control and display systems of Airbus A380. In the synchronous programming framework, the computations (in particular computations about time) are considered to have zero duration which, in practice, is acceptable as long as operations have a bounded duration. An in-depth introduction to the synchronous paradigm resulting of this hypothesis may be found in [START_REF] Benveniste | The Synchronous Approach to Reactive and Real-time Systems[END_REF].

Problem statement. The analysis presented in this paper considers the Signal language as part of the instrumentation of the Eclipse project POP 1 within a translation validation tool chain [START_REF] Ngo | Formal Verification of Synchronous Data-flow Program Transformations Toward Certified Compilers[END_REF]. The Signal compiler constructs the data dependencies among signals in a program, represented as a labeled directed graph, in which the labels are polynomials in Z/ 3 Z. Then for each dependency cycle in the graph, it checks the product of the cycle labels. If this product, which is represented as a polynomial, is equal to the null clock, then it does not stand for a deadlock. However, consider the sampling operator y := x when b, in which the clock of the signal y is defined by the condition clock [b], which defines the instants where b is present and has value true. If the Boolean expression b is a non Boolean relation (e.g. a comparison between numerical expressions), then the Z/ 3 Z abstraction considers the expression's clock instead. This yields an approximation 1 Polychrony on Polarsys: an Eclipse project of the Polarsys Industry Working Group, http://www.polarsys.org/projects/polarsys.pop of the actual dependency which may cause the compiler to approximate dependencies, like in the example above.

Contribution. We propose a more precise deadlock detection approach for deadlock-free checking of synchronous programs defining multi-clocked embedded real-time systems in the Signal language. Our approach permits the compiler to detect deadlocks more precisely when dealing with numerical expressions. In our solution, the data dependencies among signals are represented by Synchronous Data-flow Dependency Graphs (SDDGs). A SDDG is a labeled directed graph in which each node is a signal or clock variable and each edge represents a dependency between two nodes. Each edge is labelled by a condition at which the dependency is effective. We borrow the Boolean-interval abstraction from [START_REF] Feautrier | Enhancing the Compilation of Synchronous Data-flow Programs with Combined Numerical-Boolean Abstraction[END_REF] to encode the clock labels. That means every signal is associated with a pair of the form (clock, value), where clock is a Boolean function and value is a Boolean or numerical function, abstracted as an interval. We use a SMT solver to reason on the labels when deciding a dependency cycle in a SDDG to stand for a deadlock. We show how our approach addresses the limitation of the current deadlock detection used in the Signal compiler through a concrete example.

Outline. The remainder of this paper is organized as follows. Section II introduces the Signal language. Section III provides an overview of the current deadlock detection approach used in the Signal compiler and shows its limitation when dealing with numerical expressions. In Section IV, we present the concept of SDDG as well as the Boolean-interval abstraction and deadlock detection in SDDGs. This section also shows how we use a SMT solver to implement the detecting deadlock procedure. Section V presents related works and concludes.

II. THE SIGNAL LANGUAGE

Signal is a polychronous data-flow language that allows the specification of multi-clocked systems, called polychrony model. Signal handles unbounded sequences of typed values x(t) t∈N , called signals, denoted as x. Each signal is implicitly indexed by a logical clock indicating the set of instants at which the signal is present, noted C x . At a given instant, a signal may be present where it holds a value, or absent where it holds no value (denoted by #). Given two signals, they are synchronous if and only if they have the same clock. In Signal, a process (written P or Q) consists of the synchronous composition (noted |) of equations over signals x, y, z, written x := y op z or x := op(y, z), where op is an operator. Then a program is a process and the language is modular. In particular, a process can be used as a basic pattern, by means of an interface that describes its parameters and its input and output signals. Moreover, a process can use other subprocesses, or even external parameter processes that are only known by their interfaces. Data Domains. Data types consist of usual scalar types (Boolean, integer, float, complex, and character), enumerated types, array types, tuple types, and the special type event, subtype of the Boolean type which has only one value, true.

Operators. The core language consists of two kinds of "statements" defined by the following primitive operators: four operators on signals and two operators on processes. The operators on signals define basic processes (with implicit clock relations) while the operators on processes are used to construct complex processes with the parallel composition operator: • Delay: y := x$1 init a defines a basic process such that y and x are synchronous, y(0) = a, and ∀t ∈ C y ∧ t > 0, y(t) = x(t -1).

• Stepwise Functions: y := f (x 1 , ..., x n ),
• Merge: y := x def ault z defines a basic process which specifies that y is present if and only if x or z is present, and that

y(t) = x(t) if t ∈ C x and y(t) = z(t) if t ∈ C z \ C x .
• Sampling: y := x when b where b is a Boolean signal, defines a basic process such that ∀t ∈ C x ∩C b ∧b(t) = true, y(t) = x(t), and otherwise, y is absent.

• Composition: If P 1 and P 2 are processes, then P 1 | P 2 , also denoted as (|P 1 | P 2 |), is the process resulting of their parallel composition. This process consists of the composition of the systems of equations. The composition operator is commutative, associative, and idempotent.

• Restriction: P where x, where P is a process and x is a signal, specifies a process by considering x as local variable to P (i.e., x is not accessible from outside P ).

Clock Relations. Clock relations can be defined explicitly: y := ˆx specifies that y is the clock of x. In this program, x, c and v at lines (2) and (3) are respectively input and output signals of type integer. Line (4) expresses that y holds the value of v if v, c are present and c is less than or equal to 0, otherwise it holds the value of x when x is present. At line [START_REF] Biere | Handbook of Satisfiability[END_REF], u, y, x are constrained to be synchronous. And u is set to the sum of y and x when y and x are present. Line [START_REF] Barrett | The Satisfiability Modulo Theories Library (SMT-LIB)[END_REF] defines that v is set to u when c is greater than or equal to 1. Line [START_REF] Gamatié | Designing Embedded Systems with The Signal Programming Language: Synchronous, Reactive Specification[END_REF] indicates that y and u are local signals. A possible run of the program is depicted by the following trace:

1 x 1 3 2 2 # # 4 7 9 ... 2 c 1 3 0 1 -1 -

III. DEADLOCK DETECTION IN THE SIGNAL COMPILER

Before generating the executable code on a given architecture, the compilation performed by the Signal compiler aims at proving the reactivity and the determinism of programs by modeling the synchronization relations and checking the absence of cyclic data dependencies in program specifications. In our consideration, the compiler needs to answer the following question: "Is the program deadlock-free". To answer this question, the Signal compiler uses the Graph of Conditional Dependencies (GCD) in which a dependency between data is conditioned by a clock. We will illustrate this technique with an example (a more detailed discussion is presented in [START_REF] Maffeïs | Distributed Implementation of Signal: Scheduling and Graph clustering. Formal Techniques in Real-Time and Fault-Tolerant Systems[END_REF]).

The Synchronization Space. The state of a Boolean signal x can be encoded in the finite field Z/ 3 Z of integers modulo 3 as the following values: -1: present and false, 1: present and true, and 0: absent. Then, the clock of the signal x may be clearly represented by x 2 . For non-Boolean signals: their presence is encoded as 1 and their absence as 0. This principle is used to represent synchronization relations in a Signal program. The coding of the primitive operators is deduced from their definition as described in [START_REF] Gamatié | Polychronous Design of Embedded Real-time Applications[END_REF]. For instance, applying this principle on program CycleDependency, we have the following algebraic coding, where we introduce three fresh variables c 1 , c 2 and v 1 to replace the expressions (c <= 0), (c >= 1) and (v when c 1 ): Limitations. Based on GCD graphs, the Signal compiler identifies the potential deadlocks in the program. Such a bad dependency between signals will appear as a cycle in the graph if the product of the labels of its edges is not the null clock. Then, we say that there exists a deadlock in the program. The deadlock detection can be performed on a GCD

y 2 = v 2 1 + (1 -v 2 1 )x 2 ; v 2 1 = v 2 (-c 1 -c 2 1 ) u 2 = y 2 = x 2 ; c 2 1 = c 2 = c 2 2 ; v 2 = u 2 (-c 2 -c 2 2 ) Graph of
u v v1 y u 2 (-c2 -c 2 2 ) v 2 (-c1 -c 2 1 ) v 2 1 u 2
Fig. 1: Dependencies among y, u, v as follows. Given a GCD, we say that the graph is deadlockfree iff for every cycle (x 1 , ..., x n , x 1 ) in the graph, the product of c 1 , ..., c n is the null clock (equal to 0), where c i is the label of the edge between x i and x i+1 , and c n is the label of the edge between x n and x 1 . However, for the sampling operator y := x when b, if the Boolean expression b is a non Boolean relation, then the Z/ 3 Z encoding considers this condition clock as an indeterminate value. This naturally yields over-approximated detection when dealing with non Booleans values.

The CycleDependency program and its dependencies among the signals y, u and v in Figure 1 exemplifies the over-approximated detection (we omit the dependencies among v, v 1 , y and u). These dependencies introduce a cycle in the graph. To verify that this cycle is not a deadlock, the Signal compiler calculates the product of the labels as

x 2 (-c 2 - c 2 2 )(-c 1 -c 2 1 ) * x 2 (-c 2 -c 2 2 )(-c 1 -c 2 1 ) * x 2 * x 2 (-c 2 -c 2 2
). With the current clock calculus, the compiler concludes that this cycle may cause a deadlock since at some instants the above product is different from 0 (e.g. when the signals x, c 1 , c 2 are present and both c 1 and c 2 hold the value true, or x 2 = 1, c 1 = 1, and c 2 = 1). But in fact, c 1 and c 2 cannot hold the value true at the same time.

The above limitation makes the Signal compiler reject some possibly valid programs. To address this issue, we propose a new deadlock detection to better handle numerical operators.

IV. A MORE PRECISE DEADLOCK DETECTION

In this section, we will present a more precise deadlock detection technique compared to the technique currently used by the Signal compiler. This technique uses the concept of Synchronous Data-flow Dependency Graph (SDDG) to express the data dependencies among the signals in a program. A SDDG represents a synchronous program as a labelled directed graph in which each node is a signal or a clock and each edge from a node to another node represents the dependency between nodes. Each edge is labeled by a clock constraint. The abstraction which is used to encode the clock constraints was originally proposed by Gamatié et al. [START_REF] Feautrier | Enhancing the Compilation of Synchronous Data-flow Programs with Combined Numerical-Boolean Abstraction[END_REF].

A. Signal Program as Synchronous Data-flow Dependency Graph 1) A Boolean-interval Abstraction for Clock Semantics:

Let X = {x 1 , ..., x n } be the set of all signals in program P . With each signal x i , we attach a Boolean variable x i to encode its clock and a variable x i of same type as x i to encode its value. Formally, the abstract values which represent the semantics of the program can be computed using the following functions: ˆ: X -→ B associates a signal with a Boolean value ˜: X -→ D associates a signal with a value of the same type

The composition of Signal processes corresponds to logical conjunctions. Thus the abstract model of P will be a conjunction Φ(P ) = n i=1 φ(eq i ) whose atoms are x i , x i , where φ(eq i ) is the abstraction of statement eq i (statement using the Signal primitive operators), and n is the number of statements in the program. In the following, we present the abstraction corresponding to each Signal operator. There are two definitions of Φ according to the type of the signal on the left hand side in each equation: (1) stands for numerical type and ( 2) is for logical type. The Boolean-interval abstraction preserves the behaviors of the program being abstracted, in other word, it is sound. The details of the abstraction and the soundness proof are presented in [START_REF] Feautrier | Enhancing the Compilation of Synchronous Data-flow Programs with Combined Numerical-Boolean Abstraction[END_REF].

Stepwise Functions. The functions which apply on signal values in the primitive stepwise functions are usual logic operators (not, and, or), numerical comparison functions (<, > , =, <=, >=, / =), and numerical operators (+, -, * , /) (denoted by ). In our implementation, we replace the operation results by intervals and their representation in logic context by uninterpreted functions.

The abstraction φ(y := f (x 1 , ..., x n )) of stepwise functions is defined as follows:

n i=1 (ŷ ⇔ xi ) ∧ (ŷ ⇒ ỹ ∈ φ(f (x 1 , ..., x n ))) (1) n i=1 (ŷ ⇔ xi ) ∧ (ŷ ⇒ ỹ ⇔ φ(f (x 1 , ..., x n ))) (2)
where the abstraction φ(f (x 1 , ..., x n ) is defined by induction as follows: φ(true) = true and φ(false

) = false; φ(x) = x if x is of Boolean type, φ(x) = true if x is of event type; φ(x) = inv(x) if x is of non-Boolean type, where inv(x) is the interval of x; φ(x 1 and x 2 ) = x 1 ∧ x 2 ; φ(x 1 or x 2 ) = x 1 ∨ x 2 ; φ(not x 1 ) = ¬ x 1 ; φ(x <= c) = x ∈ (-∞, c], φ(x < c) = x ∈ (-∞, c); φ(x 1 <= x 2 ) = (x ∈ φ(x 1 - x 2 ))∧ x ∈ (-∞, 0]
, where x is a fresh variable; φ(x 1 x 2 ) = (φ(x 1 ), φ(x 2 )), an approximation of numerical operations on intervals, corresponding to as in [START_REF] Alefeld | Introduction to Interval Computation[END_REF]. For example, for addition operation i +j ≡ [i -+ j -, i + + j + ], where i -and i + are respectively the lower and upper bounds of the interval i.

Delay. The encoding of the delay is given as follows. This encoding requires that at any instant, signals x and y have the same clock. If they are numerical signals, then they have the same interval. Otherwise, we introduce a memorization variable m.x that stores the last value of x. The next value of m.x is m.x and it is initialized to a in m.x 0 .

(ŷ ⇔ x) ∧ (ŷ ⇒ (ỹ ∈ φ(x) ∨ ỹ = a)) (1) (ŷ ⇔ x) ∧ (ŷ ⇒ (ỹ ⇔ m.x ∧ m.x ⇔ x)) ∧ ( m.x 0 ⇔ a) (2)
Merge and sample. The encoding of the merge and sample contributes to Φ(P ) with the following propositions, respectively:

(ŷ ⇔ x ∨ ẑ) ∧ (ŷ ⇒ (x ∧ (ỹ = x)) ∨ (¬x ∧ (ỹ = z))) (1) (ŷ ⇔ x ∨ ẑ) ∧ (ŷ ⇒ (x ∧ (ỹ ⇔ x)) ∨ (¬x ∧ (ỹ ⇔ z))) (2) and (ŷ ⇔ (x ∧ b ∧ b)) ∧ (ŷ ⇒ (ỹ = x)) (1) (ŷ ⇔ (x ∧ b ∧ b)) ∧ (ŷ ⇒ (ỹ ⇔ x)) (2)
Composition φ(P 1 |P 2 ) is defined by φ(P 1 ) ∧ φ(P 2 ).

Clock Relations. Given the above rules, we can obtain the following abstraction for derived operators on clocks. Here, z is a signal of type event. φ(z

:=ˆx) = (ẑ ⇔ x) ∧ (ẑ ⇒ z); φ(x ˆ= y) = x ⇔ ŷ; φ(z := x ˆ+ y) = (ẑ ⇔ (x ∨ ŷ)) ∧ (ẑ ⇒ z); φ(z := xˆ * y) = (ẑ ⇔ (x ∧ ŷ)) ∧ (ẑ ⇒ z); φ(z := x ˆ-y) = (ẑ ⇔ (x ∧ ¬ŷ)) ∧ (ẑ ⇒ z); φ(z := when b) = (ẑ ⇔ ( b ∧ b)) ∧ (ẑ ⇒ z).
Example. Assume that the variant intervals for program signals are given as x ∈ (-∞, +∞), c ∈ (-∞, +∞), y ∈ (-∞, +∞), u ∈ (-∞, +∞), v ∈ (-∞, +∞). Applying the abstraction rules above, the abstraction of the CycleDependency program is represented by the following first-order logic formula:

(ŷ ⇔ v 1 ∨ x) ∧ (ỹ ∈ (-∞, +∞)) ∧ ( v 1 ⇔ v ∧ c 1 ∧ c 1 ) ∧ ( v 1 ∈ (-∞, +∞)) ∧ ( c 1 ⇔ ĉ) ∧ ( c 1 ⇔ (c ∈ (-∞, 0])) ∧ (û ⇔ ŷ ⇔ x) ∧ (ũ ∈ (-∞, +∞)) ∧ (v ⇔ û ∧ c 2 ∧ c 2 ) ∧ (ṽ ∈ (-∞, +∞)) ∧ ( c 2 ⇔ ĉ) ∧ ( c 2 ⇔ (c ∈ [1, +∞)))
2) Synchronous Data-flow Dependency Graph: Consider the basic process y := x def ault z (and the clock relations among the signals), the "valid" states are: x is present and y is present; or x is absent, z is present, and y is present; or x, y and z are absent. They can be represented by ŷ ⇔ (x ∨ ẑ) in our Boolean-interval abstraction. According to the valid states of the signals, the different data dependencies among signals in the basic process y := x def ault z are depicted in Figure 2, where the labels represent the conditions at which the dependencies are effective. For instance, when x = true, y is defined by x; otherwise it is defined by z when x = false and ẑ = true. We can see that the graph in this figure has the following property: an edge cannot exist if one of its extremity nodes is not present (or the corresponding signal holds no value). In our example, this property can be expressed in the abstraction as:

x ⇒ ŷ ∧ x; ¬x ∧ ẑ ⇒ ŷ ∧ ẑ. A SDDG a given program is a labelled directed graph y x z x ¬x ∧ ẑ
Fig. 2: The SDDG of Merge Operator in which each node is a signal or clock variable and each edge represents the dependency between nodes. Each edge is labelled by a first-order logic formula which represents the clock at which the dependency between the extremity nodes is effective. Formally, a SDDG is defined as follows: E,I,O,C,m N ,m E where:

Definition 1: A SDDG associated with a process P is a tuple G = N,
• N is a finite set of nodes, each of which represents the equation defining a signal or a clock;

• E ⊆ N ×N is the set of dependencies between nodes;

• I ⊆ N is the set of input nodes;

• O ⊆ N is the set of output nodes;

• C is the set of first-order logic formulas over a set of clocks in the Boolean-interval abstraction;

• m N : N -→ C is a mapping labeling each node with a clock; it defines the existence condition of a node;

• m E : E -→ C is a mapping labeling each edge with a clock constraint; it defines the existence condition of an edge.

Operator Dependencies

x x x -→ x, m N (x) = x, m N (x) = x c (Boolean signal) c [c] --→ [c], m N (c) = ĉ, m N ([c]) = [c] c [¬c] ---→ [¬c], m N (c) = ĉ, m N ([¬c]) = [¬c] x c -→ y [c] [c] --→ y, m N ([c]) = [c], m N (y) = ŷ y := f (x1, ..., xn) x1 ŷ -→ y ... xn ŷ -→ y m N (xi) = xi, m N (y) = ŷ, i = 1, ..., n y := x$1 init a m N (x) = x, m N (y) = ŷ y := x when b x ŷ -→ y, m N (x) = x, m N (y) = ŷ b ŷ -→ ŷ, m N (b) = b, m N (ŷ) = ŷ y := x default z x x -→ y, m N (x) = x, m N (y) = ŷ z ẑ∧¬x ----→ y, m N (z) = ẑ, m N (y) = ŷ
= {x 0 , x 1 , ..., x k } such that x = x 0 c0 -→ x 1 c1 -→ ... c k-1 ---→ x k = y.
In Table I, we construct the dependencies among signals for the core language, where the sub-clocks [c] and [¬c] are encoded as ĉ ∧ c and ĉ ∧ ¬c, respectively, in our abstraction. The edges are labelled by clocks which are represented by a first-order logic formula in our abstraction. The dependencies in this table impose the implicit properties for a SDDG, for instance, the basic process y := x when b corresponding to the primitive operator Boolean sampling satisfies ŷ ⇒ x ∧ ŷ and ŷ ⇒ b ∧ ŷ.

We also assume that all considered programs are written with the primitive operators, meaning that derived operators are replaced by their definition with primitive ones, and there are no nested operators (these nested operators can be broken by using fresh signals).

Following the above construction rules, we can obtain the SDDG in Figure 3, for the simple program CycleDependency (we omit the parts of graph that represent the dependencies of c 1 and c 2 on c). In this graph, the clock labels are defined in the above Boolean-interval abstraction.

v u v1 y c2 c1 x v1 v1 v û ¬ v1 ∧ x û v v1
Fig. 3: The SDDG of CycleDependency

B. Precise Deadlock Detection

In this section, we will present a more precise deadlock detection technique which is based on the concept of SDDG along with the Boolean-interval abstraction. We will show a performance comparison of our technique with the current technique of the Signal compiler using a concrete example.

1) Deadlock Definition:

Let G be a SDDG, and x ĉ -→ y be an edge in G. Assume that there exists a path from y to x, that forms a dependency cycle between x and y. A cycle of dependencies, standing for a deadlock, is defined with a similar meaning to the one in GCD. We say that such cycle is a deadlock in G iff the dependencies of x to y and viceversa are effective at the same time. Transposing the notion of deadlock to SDDG graphs, we have the following definition:

Definition 2: Let G = N, E, I, O, C, m N , m E be a SDDG; a cycle p c = x 1 , ..., x n , x 1 in G is said a dead- lock if there exists an interpretation such that the formula m E (x 1 , x 2 ) ∧ m E (x 2 , x 3 ) ∧ ... ∧ m E (x n , x 1 ) is true.
Based on the definition of deadlock in SDDG graphs, we can have a consequent definition of deadlock-free of a SDDG as follows:

Definition 3: An SDDG G = N, E, I, O, C, m N , m E is deadlock-free iff every cycle (x 1 , ..., x n , x 1 ) in G satisfies: m E (x 1 , x 2 ) ∧ m E (x 2 , x 3 ) ∧ ... ∧ m E (x n , x 1 ) ⇔ false
Obviously, the fact that the conjunction of first-order logic formulas, in which the dependencies are effective when they are valid, is false indicates that a deadlock does not exist if all the dependencies of a cycle in the SDDG graph cannot be present at the same time.

2) Proving Deadlock Freedom by SMT Solver: Given the SDDG of a program P , we introduce an approach to check whether the graph is deadlock-free. It is implemented with a SMT solver [START_REF] Dutertre | Yices sat-solver[END_REF], [START_REF] Stump | SMT-Comp[END_REF]. A SMT solver decides the satisfiability of arbitrary logic formulas of linear real and integer arithmetic, scalar types, other user-defined data structures, and uninterpreted functions. If formula belongs to the decidable theory, the solver gives two types of answers: sat when the formula has a model (there exists an interpretation that satisfies it); or unsat otherwise. In our case, the formulas which label the edges of the graph are over Boolean variables and uninterpreted functions, thus the solving is decidable and very efficient [START_REF] Ackerman | Solvable cases of the Decision Problem[END_REF], [START_REF] Biere | Handbook of Satisfiability[END_REF].

Following Definition 3, we will traverse the entire graph to find all cycles and verify that every cycle does not stand for a deadlock. Notice that here, we do not provide any specific algorithm to find the cycles in a directed graph, interested readers can refer to any research on this problem (e.g. the work of D.B. Johnson [START_REF] Johnson | Finding All the Elementary Circuits of A Directed Graph[END_REF]). It means that the basic element we have to prove is that given a dependency cycle and the conjunction of its labels, this conjunction formula is always evaluated to the value false.

Consider a dependency cycle

x 1 → c1 x 2 → c2 ... → cn-1
x n → cn x 1 . This cycle does not stand for a deadlock iff the formula n i=0 c i ⇔ false is valid within the logical context defined by the abstraction of P . The checking of this condition can be implemented by asking a SMT solver to check M |= ¬( n i=0 c i ⇔ false). Based on our experience with SMT solvers, it is more efficient to make the conjunction of all formulas such as n i=0 c i ⇔ false and call the solver once.

3) Implementation and Illustrative Example: We describe the main steps of our approach, and the techniques we use to implement them. The tool's flow is depicted in Figure 4. First, it takes the input program P , and constructs the corresponding SDDG graph. It finds all cycles in the graph. Finally, in the solving phase, it checks the validity of the formula ( n i=0 c i ⇔ false) for each cycle (x 1 , ..., x n , x 1 ). Interval Analyzer. This step determines the interval of every For every input signal, it is assumed that its interval is known. This step applies the algorithm presented in [START_REF] Gonnord | Abstract Acceleration to Improve Precision on Linear Relation Analysis[END_REF]. The tool in [START_REF] Lalire | Interproc: An Interprocedural Analyzer for Imperative Languages[END_REF] is used to compute an over-approximation of the variation interval of each numerical signal.

Abstraction. The input program is encoded according to the Boolean-interval abstraction scheme in Section IV-A1. The output of this step is a first-order logic formula. SDDG Construction. After obtaining the interval analysis and the abstract model of the input program, this step will construct the corresponding SDDG graph according to the rules in Table I. The labels of edges in the graph are encoded as first-order logic formulas based on the above Boolean-interval abstraction scheme. In this step, the tool also detects all dependency cycles in the graph and produces the conjunction formula of all clock labels for each cycle as input for the solver. SMT-based Proof. We delegate checking the validity of the formulas to a SMT solver. Our implementation uses the SMT-LIB common format [START_REF] Barrett | The Satisfiability Modulo Theories Library (SMT-LIB)[END_REF] to encode the formulas as input to the SMT solver. For our experiments, we consider the Yices [START_REF] Dutertre | Yices sat-solver[END_REF] solver, which is one of the best solvers at the SMT-COMP competition [START_REF] Stump | SMT-Comp[END_REF].

Let us illustrate the above deadlock detection technique on the CycleDependency program. In the first step, we will determine the variation interval for all signals in the program. We assume that the variation intervals for input signals x and c are (-∞, +∞), (-∞, +∞). After the analysis, we get:

x ∈ (-∞, +∞), c ∈ (-∞, +∞), y ∈ (-∞, +∞), u ∈ (-∞, +∞), v ∈ (-∞, +∞).
In the second step, Booleaninterval abstraction, our tool will translate the program into a logic formula Φ according to the above abstract scheme. Let us focus on the clocks of signals y, u, and v, which are given as follows:

ŷ ⇔ v 1 ∨ x; û ⇔ ŷ ⇔ x; c 1 ⇔ c 2 ⇔ ĉ v 1 ⇔ v ∧ c 1 ∧ (c ∈ (-∞, 0]); v ⇔ û ∧ c 2 ∧ (c ∈ [1, +∞))
In the third step, we construct the SDDG graph in Figure 3. Here, we detect that there exists a dependency cycle (v, v 1 , y, u, v) in the graph, the tool then generates the formula ( v 1 ∧ v 1 ∧ û ∧ v) ⇔ false , referred to as ϕ, to delegate to the SMT solver. In the logical context defined by Φ, replacing the definitions of c 1 , c 2 , û, v and v 1 in the program abstraction model, we get:

(x ∧ ĉ ∧ (c ∈ [1, +∞)) ∧ ĉ ∧ (c ∈ (-∞, 0]) ∧ x ∧ ĉ ∧ (c ∈ [1, +∞)) ∧ ĉ ∧ (c ∈ (-∞, 0]) ∧ x ∧ x ∧ ĉ ∧ (c ∈ [1, +∞))) ⇔ false
With the Yices solver, we will get unsat when checking the satisfiability of ¬ϕ, which means that ϕ is valid. Thus, the graph is deadlock-free.

Our deadlock detection technique is more precise than the current technique used by the Signal compiler when dealing with numerical expressions. It admits less erroneous (or "spurious") decision on deadlock detection than the current technique. That means that when our approach is applied on the Signal compiler, it will make the compiler avoid rejecting valid programs. The reason why our technique is more expressive than the current one is that it uses a more suitable and precise abstraction for numerical expressions. For instance, here, our tool can detect that the two signals v and v 1 cannot be present at the same time.

V. CONCLUSION AND RELATED WORK

The concept of interval-Boolean abstraction was introduced in [10] by A. Gamatié et al. to provide a more efficient static analysis of Signal compiler. In that work, the authors aim to make the analysis of clock hierarchy more powerful when dealing with the numerical expressions. The analysis presented in this paper is implemented as part of the instrumentation of the Eclipse project POP on synthesizing safety wrappers for polychronous specifications through polyhedral analysis, and generalizes the work presented in [START_REF] Jose | SMT based false causal loop detection during code synthesis from polychronous specifications[END_REF] on false-loop detection using SMT-solving to the case of a polyhedral analysis.

A relevant study on synchronous data-flow dependency graph [START_REF] Ngo | Formal Verification of Synchronous Data-flow Program Transformations Toward Certified Compilers[END_REF] concerns the preservation of data dependency in the transformation of Signal programs during the compilation process. In that work, the authors represent the data dependencies in the source synchronous program and the compiled program as labelled directed graphs, in which the edges are labeled by first-order logic formulas. Given two graphs, a correct transformation relation between them is defined, which expresses the semantic preservation of data dependency. In implementation, a SMT-solver is used for checking the existence of the correct transformation relations. This validation is applied to the second compilation phase of the Signal compiler, static scheduling.

In this paper, we propose a more precise deadlock detection approach for deadlock-free checking of synchronous programs written in Signal language. Our approach permits the compiler avoiding emitting spurious decision on deadlock detection while the current technique does when dealing with numerical expressions. In our solution, the data dependencies among signals are represented by SDDG graphs, in which the nodes are signals or clock variables, edges are dependencies among signals. Each edge is labeled by a condition expressed as a first-order logic formula at which the dependency is effective. We use a SMT solver to reason on the labels when deciding whether a dependency cycle in a SDDG stands for a deadlock. We have provided a technique to implement and integrate our deadlock detection approach within the Polychrony toolset with Yices. As next work, we will do some enhancement of the implementation by making it a fully automated process. We will take more case studies as well.

1 process CycleDependency= 2 (

 12 ? integer x, c; ! integer v) 3 (| y := (v when (c <= 0)) default x 4 | u := y + x 5 | v := u when (c >= 1) 6 |) 7 where integer y, u end;

  Conditional Dependencies. The GCD calculated by the Signal compiler is a labeled directed graph where the vertices are the signals and clock variables, the edges indicate data dependencies among signals and clock variables, the labels are polynomials on Z/ 3 Z which represent the conditions at which the dependencies are valid. In case of the program CycleDependency, the dependencies among signals y, u and v are depicted as the sub-graph in Figure 1. The notation x → c 2 y means that at a given instant, y depends on x iff c 2 = 1.

Fig. 4 :

 4 Fig. 4: Block diagram of the analytic flow

  The synchronization xˆ= y means that x and y have the same clock. The clock extraction from a Boolean signal is denoted by a unary when: when b. The clock union xˆ+ y defines a clock as the union C x ∪ C y . In the same way, the clock intersection x ˆ * y and the clock difference xˆ-y define clocks C x ∩ C y and C x \ C y .

	Example. The following Signal program illustrates the lan-
	guage syntax and meaning of primitive operators. It emits an
	integer sequence v whose ith value v i is the double of the
	input x i depending on the other input c.

TABLE I :

 I The Dependencies of the Core Language

	The clock labeling in SDDG provides a dynamic dependency
	feature. This clock imposes the following property: An edge
	exists if its two extremity nodes exist. This property can be
	translated in our Boolean-interval abstraction as: ∀(x, y) ∈
	E, m

E (x, y) ⇒ (m N (x) ∧ m N (y)). We denote the fact that there exists a dependency between two nodes (signals or clocks) x and y at a clock condition m E (x, y) = ĉ by x ĉ -→ y. A dependency path from x to y is any set of nodes s


Formal Indistinguishability extended to the Random Oracle Model

Cristian Ene, Yassine Lakhnech and Van Chan Ngo �

Université Grenoble 1, CNRS,Verimag

There are two main frameworks for analyzing cryptographic systems; the symbolic framework, originating from the work of Dolev and Yao, and the computational approach, growing out of the work of Goldwasser and Micali. A significant amount of effort has been made in order to link both approaches and profit from the advantages of each of them. Indeed, while the symbolic approach is more amenable to automated proof methods, the computation approach can be more realistic. Abadi and Rogaway were the first to prove a formal link between these two models. More precisely, they introduced an equivalence relation on terms and prove that equivalent terms correspond to indistinguishable distributions ensembles, when interpreted in the computational model. The work of Abadi and Rogaway has been extended to active adversaries and various cryptographic primitives.

Related works.

A recently emerging branch of relating symbolic and computational models for passive adversaries is based on static equivalence from π-calculus, induced by an equational theory. Equational theories provide a framework to specify algebraic properties of the underlying signature, and hence, symbolic computations in a similar way as for abstract data types. That is, for a fixed equational theory, a term describes a computation in the symbolic model. Thus, an adversary can distinguish two frames (which roughly speaking are tuples of terms), if he is able to come up with two computations that yield the same result when applied to one frame, but different results when applied to the other frame. Such a pair of terms is called a test. Thus, a static equivalence relation is fully determined by the underlying equational theory, as two frames are statically equivalent, if there is no test that separates them. Baudet, Cortier and Kremer studied soundness and faithfulness of static equivalence for general equational theories and used their framework to prove soundness of exclusive or as well as certain symmetric encryptions. Abadi et al. used static equivalence to analyze guessing attacks.

Recently, Bana, Mohassel and Stegers argued that even though static equivalence works well to obtain soundness results for the equational theories mentioned above, it does not work well in other important cases. Consider for instance the Decisional Diffie Hellman assumption (DDH for short) that states that the tuples (g, g a , g b , g ab ) and (g, g a , g b , g c ), where a, b, c are randomly sampled, are indistinguishable. It does not seem to be obvious to come up with an equational theory for group exponentiation such that the induced static equivalence includes this pair of tuples without including others whose computational indistinguishability is not proved to be a consequence of the DDH assumption. The static equivalence induced by the standard equational theory for group exponentiation includes the pair (g, g a , g b , g a 2 b ) and (g, g a , g b , g c ).

It is unknown whether the computational indistinguishability of these two distributions can be proved under the DDH assumption. Therefore, Bana et al. propose an alternative approach to build symbolic indistinguishability relations: a formal indistinguishability relation (FIR) is defined as a closure of an initial set of equivalent frames with respect to simple operations � Grenoble, email:name@imag.fr This work has been partially supported by the ANR projects SCALP, AVOTE and SFINCS which correspond to steps in proofs by reduction. This leads to a flexible symbolic equivalence relation. In order to prove soundness of a FIR it is enough to prove soundness of the initial set of equivalences. Moreover, static equivalence is one instance of a FIR. Contributions. In this paper, we extend Bana et al.'s approach by introducing a notion of symbolic equivalence that allows us to prove computational security of encryption schemes symbolically. More specifically, we would like to be able to treat generic encryption schemes that transform one-way functions to IND-CPA secure encryption schemes. Therefore, three problems need to be solved. First, we need to cope with one-way functions. This is another example where static equivalence does not seem to be appropriate. It does not seem easy to come with a set of equations that capture the one-wayness of a function. Indeed, consider the term f (a|b), where f is a one-way function and | is bit-string concatenation. We know that we cannot easily compute a|b given f (a|b) for uniformly sampled a and b. However, nothing prevents us from being able to compute a for instance. Introducing equations that allow us to compute a from f (a|b), e.g., g(f (a|b)) = a, may exclude some one-way functions and does not solve the problem. Nothing prevents us from computing a prefix of b, a prefix of the prefix, etc . . . . The second problem that needs to be solved is related to the fact that almost all practical provably secure encryption schemes are analyzed in the random oracle model. The random oracle model is an idealized model in which hash functions are randomly sampled functions. In this model, adversaries have oracle access to these functions. An important property is that if an adversary is unable to compute the value of an expression a and if H(a) has not been leaked behore, then H(a) looks like a uniformly sampled value. Thus, we need to be able to symbolically prove that a value of a given expression a cannot be computed by any adversary. This is sometimes called weak secrecy in contrast to indistinguishability based secrecy. To cope with this problem, our notion of symbolic indistinguishability comes along with a non-derivability symbolic relation. Thus in our approach, we start from an initial pair of a non-derivability relation and a frame equivalence relation. Then, we provide rules that define a closure of this pair of relations in the spirit of Bana et al.'s work. Also in our case, we prove that computational soundness of the obtained relations can be checked by checking computational soundness of the initial relations. The third problem is related to the fact that security notions for encryption schemes such IND-CPA and real-or-random indistinguishability of cipher-text under chosen plaintext involve active adversaries. Indeed, these security definitions correspond to two-phase games, where the adversary first computes a value, then a challenge is produced, then the adversary tries to solve the challenge. Static equivalence and FIR (as defined in by Bana et all.) consider only passive adversaries. To solve this problem we consider frames that include variables that correspond to adversaries. As frames are finite terms, we only have finitely many such variables. This is the reason why we only have a degenerate form of active adversaries which is enough to treat security of encryption schemes and digital signature, for instance. The advantage of defining non-deductibility as we did, and of considering FIR (instead of static equivalence) as the good abstraction of indistinguishability, is that first, we capture "just" what is supposed to be true in the computational setting, and second, if we add more equations to our abstract algebra in a coherent manner with respect to the initial computational assumptions, then our proofs still remain computationally sound. Moreover, the closure rules we propose in our framework are designed with the objective of minimizing the initial relations which depend on the underlying cryptographic primitives and assumptions. We illustrate our framework by proving IND-CPA security of the constructions of Bellare-Rogaway, Hash El Gamal and an encryption scheme proposed by Pointcheval.