Julia Cagé
email: cage@fas.harvard.edu

Lucie Gadenne
email: l.gadenne@ucl.ac.uk

Alberto Alesina

Tim Besley

Denis Cogneau

Emmanuel Farhi

Walker Hanlon

Wojciech Kopczuk

Marc Melitz

Nathan Nunn

Thomas Piketty

Romain Rancière We

Thomas Baunsgaard

Tax Revenues, Development, and the Fiscal Cost of Trade Liberalization, 1792-2006

This paper puts the recent evolution of tax revenues in developing countries in historical perspective. Using a novel dataset on total and trade tax revenues we compare the fiscal cost of trade liberalization in developing countries and in today's rich countries at earlier stages of development. We find that trade liberalization episodes led to larger and longerlived decreases in total tax revenues in developing countries since the 1970s than in rich countries in the 19th and early 20th centuries. The fall in total tax revenues lasts more than ten years in half the developing countries in our sample.

Introduction

This paper documents the fiscal cost of trade liberalization: the extent to which countries are able to recover the trade tax revenues lost from liberalizing trade by increasing tax revenues from other sources. Our starting point is a puzzle in the recent evolution of tax revenues in developing countries: tax-to-GDP ratios decrease in these countries since 1970, in contradiction with the so-called 'Wagner's Law'1 which states that tax ratios increase over time and as countries become richer. Figure 1 presents the evolution of the share of total tax and trade tax revenues over GDP in high-income countries (hereafter HICs), middle-income countries (MICs) and low-income countries (LICs) since the 1970s. In the top panel (Figure 1a) we see that tax ratios decrease in both MICs and LICs. This is particularly striking over the period 1970-2000 during which they fall by over 2 GDP points on average in both country groups.

HICs, in contrast, experience a continuous increase in tax ratios over time. The bottom panel (Figure 1b) offers a potential explanation for this fall in tax ratios. It shows the evolution of trade tax revenues in the three country groups. The decrease in the share of trade tax revenues over GDP in MICs (2.2 GDP points) and LICs (2.5 GDP points) is large enough to explain the observed fall in tax ratios in both country groups.

We investigate the relationship between changes in total and trade tax revenues in developing countries along two dimensions. First, we ask whether countries in which trade tax revenues decrease experience a contemporary fall in total tax revenues and if yes for how long it lasts. We call this fall the fiscal cost of trade liberalization. We consider whether this cost is more frequent in LICs and MICS than in HICs since 1970, as suggested by Figure 1. Second, we turn to the historical experience of today's developed countries to determine whether the fiscal cost of trade liberalization is specific to the context in which developing countries liberalized trade since 1970.

In order to do so we construct a new dataset on tax revenues and government expenditures from a variety of historical and contemporary sources. For each of the 130 countries in our dataset we go as further back in time as possible: our dataset starts in 1792 for one country (the United States), covers 9 countries in the 19th century and 35 countries in the first half of the 20th century. It is to the best of our knowledge the most exhaustive dataset on tax revenues available to researchers.

We suggest and implement a method to identify episodes of trade liberalization and measure the contemporary change in total tax revenues. We use a fiscal definition of trade liberalization: we characterize a trade liberalization episode by a large and prolonged fall in trade tax revenues over GDP. We then study whether countries are able to replace the fall in trade tax revenues by an increase in other (domestic) tax revenues and argue that there is a fiscal cost of trade liberalization when total tax revenues fall after the start of the episode.

We say that there is fiscal recovery once total tax revenues are back to their pre-episode level.

Our method may capture decreases in trade tax revenues which are not the consequence of countries' opening to international trade. We investigate possible causes for each episode using data on tariff rates, trade volumes, exchanges rates and the history of countries' trade policies. We find that 70% of the episodes can be to linked to changes in trade policy.

We find 140 episodes of trade liberalization. Trade taxes fall by more than 3 GDP percentage points on average during these episodes. 49% of the countries have recovered the lost tax revenues 5 years after the start of the episode and we never observe a fiscal recovery in over 25% of the countries. There are clear differences by level of development in the period since 1970. The fall in total tax revenues contemporary to the episodes is larger and lasts longer in developing countries (MICs and LICs) than in rich countries (HICs). Rich countries which experience a trade liberalization episode never experience any fiscal cost whilst over 50% of developing countries do. Moreover nearly 40% of LICs (34% of MICs) are never observed recovering the lost trade tax revenues through other tax instruments. Turning to the historical (pre-1970) evidence we find that the fiscal cost of trade liberalization experienced by today's HICs at early levels of economic development is smaller and shorter-lived than the one experienced by developing countries since 1970. This cost is still larger in countries that were poorer at the start of the episode. Overall, episodes of trade liberalization are found to have a more negative impact on tax revenues in poorer countries, particularly so since the 1970s.

Our results are robust to the choices made in defining an episode of trade liberalization.

Changing the extent to which we smooth the tax data prior to identifying episodes and fiscal recovery, varying the thresholds used to define an episode and normalizing tax revenues by population instead of GDP hardly affects our results concerning the fiscal cost of trade liberalization. We also find similar results when excluding episodes for which we see that countries increased tax revenues prior to the onset of the episode, suggesting they may have chosen to pre-empt the fall in trade tax revenues by increasing domestic tax revenues beforehand.

Finally, results are similar when we consider only episodes that we can link to changes in trade policy and when we consider the episodes' impact on government expenditures. This paper is closely related to [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF] who first identified the existence of a trade-off between tax revenues and trade liberalization. Using 32 years of panel data they estimate how domestic tax revenues react to changes in trade tax revenues in the short run. They, like us, find an incomplete replacement of lost trade tax revenues in LICs.

We complement their work in several ways. First, our method abstracts from short-term comovements between domestic tax and trade tax revenues which may be unrelated to structural changes in countries' tax structures. We pay particular attention to the extent to which our conclusions are driven by our methodological choices and find that they are not. Second, our longer and more complete dataset allows us to generalize their results for today's developing countries to their complete fiscal history since independence. Third, we compare these results to the fiscal impact of trade liberalization in today's rich countries when they were at similar levels of development and elaborate on the difference between today's developing countries and the historical experience of rich countries to discuss potential explanations for the fiscal cost of trade liberalization. Finally, we consider the possibility that countries that do not recover the lost revenues from trade taxes through an increase in domestic taxes may nevertheless experience an increase in non-tax revenues (development aid for example) by studying the impact of trade liberalization not only on tax revenues but also on government expenditures.

Our results also speak to the literature explaining why tax levels and tax structures change as countries develop. Recent examples include the work by Besley andPersson (2011, 2013) in which countries' decisions to invest in tax capacity allows them to increase their tax ratios over time and to decrease their dependence on trade taxes. Others argue that as economies develop they undergo structural changes which make transactions easier to monitor and allow government to rely less on less efficient but easier to levy taxes like taxes on trade (see e.g. [START_REF] Riezman | Tariffs and Collection Costs[END_REF][START_REF] Aizenman | Inflation, Tariffs and Tax Enforcement Costs[END_REF][START_REF] Kleven | Why Can Modern Governments Tax So Much? An Agency Model of Firms as Fiscal Intermediaries[END_REF]. These theories imply that countries will decrease trade taxes once they find themselves capable of levying domestic taxes but they cannot rationalize the fiscal cost of trade liberalization. We return to this literature when discussing one possible interpretation for our results, namely that developing countries liberalized trade 'too early' from a fiscal perspective. A smaller literature discusses the conditions under which revenue-neutral reforms replacing taxes on trade by domestic taxes such as the VAT will be optimal (Keen andLigthart, 2002, 2005;[START_REF] Emran | On Selective Indirect Tax Reform in Developing Countries[END_REF]. Our results show that the typical trade liberalization reform in developing countries since 1970 was not revenue-neutral but instead lead to a decrease in total revenues. This paper contributes more generally to the growing literature on public finance and development (see for example [START_REF] Gordon | Tax Structures in Developing Countries: Many Puzzles and a Possible Explanation[END_REF][START_REF] Piketty | Income Inequality and Progressive Income Taxation in China and India, 1986-2015[END_REF][START_REF] Olken | Informal Taxation[END_REF][START_REF] Pomeranz | No Taxation without Information: Deterrence and Self-Enforcement in the Value Added Tax[END_REF][START_REF] Best | Production vs Revenue Efficiency With Limited Tax Capacity: Theory and Evidence From Pakistan[END_REF] by providing a new exhaustive dataset on the subject. 2 We assemble historical and contemporary data on tax revenues in a coherent way that allows for meaningful comparison across countries and over three centuries. We hope our dataset will be of use to researchers in this field by providing a historical perspective on how both tax ratios and tax structures change as countries develop.

The remainder of the paper is organized as follows. Section 2 describes the data used and presents descriptive statistics on taxation and development. Section 3 presents our method and results regarding the fiscal cost of trade liberalization. Section 4 discusses the results. Section 5 concludes.

2 Data and descriptive statistics

Data

We combine data on total tax revenues and trade tax revenues from three different sources:

Mitchell (2007)'s International Historical Statistics, the dataset constructed by [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF] and the International Monetary Fund's Government Finance Statistics (GFS). We digitize the data in [START_REF] Mitchell | International Historical Statistics (Europe, The Americas, Africa Asia and Oceania)[END_REF] who compiles information on governments revenues from different national sources for all countries from the earliest available date to 2006. [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF] construct a dataset on total and tax revenues in 117 countries over the period 1975-2006 using the revenue information provided by the IMF's periodic consultations with member countries. The IMF's GFS spans the period and has more limited coverage than the two other sources.

Our aim is to detect and analyze changes in total and trade tax revenues within countries over time. We therefore combine these three datasets in a way that does not allow for within country 'jumps' in the series which could be due to changes in data sources. To do so, we determine which dataset contains the largest number of observations for each country and use only data from this source for each country, unless we see a clear continuity across sources. 3 When two data sources cover different and large periods of time for a country but have different information for the time period during which they overlap we create a separate 'country' identifier for each period to avoid confounding a change in the series due to a change in the source with a real change in tax revenues. Finally, there are some gaps in the series when data is not available. We do a linear interpolation when the gaps last less than three years. When the gaps are longer (typically during wars), we drop the years for which the data is missing and create another country identifier when the series start again. We obtain a total of 5,200 observations for 130 countries from 1792 to 2006. Most of the observations come from [START_REF] Mitchell | International Historical Statistics (Europe, The Americas, Africa Asia and Oceania)[END_REF] (49% of the observations) and Baunsgaard and Keen (2010) (44%). The web Appendix describes the data in more detail. Table A lists the countries in our sample and the data sources used for every country.

We complement our analysis of tax revenues by using data on the share of government expenditures in GDP from three different sources. We use the same source for our expenditure variable as for our tax variables whenever possible. Information on expenditures is available from [START_REF] Mitchell | International Historical Statistics (Europe, The Americas, Africa Asia and Oceania)[END_REF] for most of the observations for which there is also tax information from this source. The dataset compiled by [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF] however contains no information on expenditures and the GFS dataset little information. We therefore use the IMF's World Economic Outlook (WEO) database to complement our dataset. We obtain information on the share of government expenditure in GDP for 5,036 observations for 128 countries, 54% of which from [START_REF] Mitchell | International Historical Statistics (Europe, The Americas, Africa Asia and Oceania)[END_REF], 40% from the WEO database and 6% from GFS.

We use the GDP per capita data constructed by [START_REF] Maddison | Statistics on World Population, GDP and Per Capita GDP, 1-2008 AD[END_REF] to classify countries by level of development. GDP is measured in 1990 Geary-Khamis dollars and is available for all countries for our period of interest. We classify countries by income group following the earliest available country classification from the World Bank (1987). 4 Based on this classification we say that a country is a high-income country (HIC) when its GDP per capita is above 8,000 dollars, a low-income country (LIC) when its GDP is below 2,000 dollars and a middle-income country (MIC) in between. The United States for example is a LIC until 1856, a MIC until 1941 and a HIC after that. We sometimes classify countries with respect to their GDP in 2006. When we refer to 'today's developing countries' we include all countries that are a LIC or a MIC in 2006. Classifying countries with respect to their 2006 GDP per capita our dataset includes 41 LICs, 49 MICs and 40 HICs. Countries are listed by their 2006 country group in the web Appendix Table A.

Finally, we collect data on countries' trade policies and macro-economic situations to investigate whether the episodes we identify are due to trade liberalization. We use data on average tariff rates from [START_REF] Clemens | Why did the Tariff-Growth Correlation Change afte 1950?[END_REF] which provide annual data from 1865 to 1999, and complement it with information from the United Nations' Statistical Yearbook and the World Bank's World Development Indicators.5 Data on trade volumes and exchange rates comes from the World Development Indicators. Information on the dates of entry of the different countries in our sample in regional and international trade agreements is obtained from the World Trade Organization and its Regional Trade Agreements Information System.

Finally we collect information on the historical trade policy of countries from various volumes of the Cambridge Economics Histories.

Descriptive Statistics

Table 1 shows the evolution of total and trade tax revenues as a share of GDP and GDP per capita since the 1830s for countries that are HICs, MICs or LICs in 2006. It highlights several stylized facts of interest regarding taxation and development. First, we see that tax-to-GDP ratios (hereafter tax ratios) increase with GDP per capita, in line with Wagner's Law. This is particularly evident in column 1 depicting the evolution of tax ratios for today's HICs. In the 1830s, the two countries for which data is available (the UK and the US) are what we would today call LICs and levy less than 7% of their GDP in taxes. Tax ratios then increase in the second half of the 19th century to 9% as countries become MICs and keep increasing by roughly 4-5 GDP points every twenty years until today. The trend of the first half of the 20th century, well-documented and often explained by higher demand for public spending during wars (see for example [START_REF] Lindert | Growing Public[END_REF], is maintained in the second half of the century. These findings are robust to considering only the 8 today's HICs for which data is available from the 1890s to the 1990s, as shown in the web Appendix Table B.1. The cross-sectional comparison between HICs, MICs and LICs in 2000-2006 also shows a positive, albeit weaker, correlation between economic development and tax ratios. HICs are today on average 16 times richer than LICs and levy twice as much taxes as a share of GDP.

Table 1 also illustrates a lesser-known stylized fact about taxation and development, the 'tax transition'. Countries at an early state of development rely on taxes on trade to levy a large share of their revenues, as they develop this share becomes smaller. 6 Trade taxes represent nearly 50% of total taxes on average in the HICs we observe in the 1830s (column 1). This share falls to 18% in the 1920s, 12% in the 1950s and decreases in the last 50 years to around 2% today. We observe a similar decrease in the share of trade taxes in total taxes in developing countries, where trade taxes represent more than 25% (MICs) and nearly 40% (LICs) of total taxes in the 1970s. This share decreases to less than 15% (22%) in the 2000s.

The correlation between the share of trade taxes in total tax revenues and development also holds in the cross-section: in 2000-2006, the share of trade taxes in total tax revenues is ten times bigger in LICs than in HICs.

The evidence also suggests that the tax transition took a different form in today's HICs compared to developing countries. In HICs the decrease in the share of trade taxes in total taxes is mostly due to an increase in non-trade tax revenues: from 1860 to 1980 the share of trade taxes in GDP remains roughly constant (between 1 and 2.5%) while the tax ratio strongly increases. The share of trade taxes in GDP only clearly decreases from 1980 to 2006, a period during which trade taxes already represent a negligible share of total revenues. In developing countries on the contrary the tax transition is due to a decrease in the share of trade taxes over GDP, starting from a higher level, and not to an increase in tax ratios.

Changes in the number of countries in each group may lead to spurious changes in average values over time. Focusing on the recent period during which more data for developing countries is available we see a similar pattern when we only consider the 87 countries for which we have data in each decade from 1970 to 2006 (Table 2). As discussed in the introduction tax ratios have decreased in both MICs and LICs during the 1980s and 1990s with tax ratios falling by 2 GDP points in LICs over the period. The share of trade taxes in GDP falls by nearly half in all country groups. This fall is more than enough to explain the decrease in total tax ratios over time in MICs and LICs but does not halt the increase in tax ratios in HICs. 7

3 The Fiscal Cost of Trade Liberalization

Method

We take a fiscal approach to trade liberalization. We define trade liberalization episodes by a fall in trade tax revenues as a percentage of GDP of at least 1 GDP point from a local maximum to the next local minimum. 8 Ratios of tax revenues to GDP experience short-run fluctuations that may come from exchange rate volatility, changes in the reporting period or business cycles and be unrelated to change in tax policy. We isolate the trends in our data on total tax, trade tax and expenditure as a share of GDP to avoid confounding episodes of trade liberalization with short-run correlations. Our main method uses the Hodrick-Prescott filter; we follow [START_REF] Ravn | On adjusting the Hodrick-Prescott filter for the frequency of observations[END_REF] in using a 6.25 smoothing parameter9 . We define the 'size' of an episode by the difference between the local maximum value of trade tax revenues as a percentage of GDP at the start of the episode (year s) and the following local minimum value of trade tax revenues at the end of the episode (year e). The distance between year e and year s is the 'length' of the episode.

We measure the potential fiscal cost of trade liberalization by looking at the evolution of total tax revenues as a percentage of GDP. By definition, total tax revenues are expected to fall during an episode unless countries are able to increase their tax collection from other (domestic) sources of tax revenues by an amount large enough to compensate the fall in trade tax revenues. In the absence of such an increase, we say that countries experience a fiscal cost of trade liberalization. More precisely we measure for each episode of decrease in trade tax 7 Part of the very large increase in tax ratios in HICs is due to changes in the data sources used over time. Our educated guess from comparing our data to official numbers released by countries' statistical institutes is that social security contributions are not included in the [START_REF] Mitchell | International Historical Statistics (Europe, The Americas, Africa Asia and Oceania)[END_REF] data but they are in the [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF] data. Web Appendix Table B.2 shows that the increase is smaller when we use only data from [START_REF] Baunsgaard | Tax Revenue and (or?) Trade Liberalization[END_REF].

8 We say that an observation is a local maximum (minimum) if it is higher (lower) than the preceding and following observations. revenues (i) whether total tax revenues as a share of GDP fall at the start of the episode; and

(ii) if they do, the number of years before total tax revenues come back to their level before the start of the episode. Formally, we define the 'revenue recovery' year (r) as the first year in which total tax revenues as a percentage of GDP are at least equal to their value in year s. We call the distance between year r and year s the 'recovery time'.

Figure 2 illustrates graphically how we construct the episodes, the fiscal cost and the fiscal recovery variables using the example of Guatemala for which we have data over the period . The vertical red line shows the start of the episode, the blue line its end and the green line the year of recovery. The episode starts in 1978, lasts six years and has a size of 2.4 GDP points. We observe a fiscal recovery after 23 years.

Trade liberalization is not the only possible explanation for the decreases in trade tax revenues we observe. They could also be the consequence of a fall in trade volumes, a shock to the exchange rate or a major destructive event that leads to a collapse in both trade and domestic tax collection. We use data on average tariff rates, trade volumes, exchange rates and dates of entry in regional and international trade agreements to identify potential explanations for the episodes. We argue that episodes which start during or just before a free trade agreement or which are contemporary to large decreases in average tariff rates, are episodes that are likely due to trade liberalization. 10 Our example of Guatemala in 1978 counts as one such episode: the average tariff rate fell by 30% between 1978 and 1982.

Table A in the web Appendix lists the countries in which episodes occur, episode start dates, and possible explanations for the decrease in trade tax revenues. We find that nearly 70% of the episodes can be traced back to some form of trade liberalization policy (a trade agreement, a fall in tariffs or a documented change in trade policy). Another 11% are contemporary with a fall in trade and 6% with an exchange rate shock. A few episodes could be the consequence of wars or natural disasters and we cannot find an explanation for 12 episodes.

Finally, categorizing a decrease in total tax revenues after the start of an episode as a 'fiscal cost of trade liberalization' is not appropriate if the decrease in trade tax revenues has been pre-empted. Countries may decide to increase tax revenues from domestic sources before lowering tariffs precisely to counterbalance for the coming fall in trade tax revenues.

The level of domestic tax revenues we observe at the start of the episode would then already compensate for the loss in trade tax revenues during the episode. We consider the evolution of domestic tax revenues in the years prior to the start of the episode to investigate whether such pre-emptive measures occur.

Results: Trade Liberalization Episodes

Table 3 presents descriptive statistics on our sample of 140 episodes of decreases in trade tax revenues. We consider separately the pre-and post-1970 periods and countries that were HICs, MICs and LICs at the start of the episode to investigate whether today's developing countries experienced a different fiscal cost of trade liberalization from today's HICs when they decreased trade tax revenues in the 19th and early 20th centuries. The choice of the 1970 year to split our sample is driven by the fact that for the majority of developing countries in our sample, data only becomes available a few years after independence. We report the total number of observations available in our dataset for the period and country groups under consideration to consider whether episodes are more likely in some periods and groups.

We see that the average potential loss in tax revenues due to an episode is large: trade tax revenues fall on average by 3.2 GDP points during the episode (column 1). This fall represents 58% of the average trade tax revenues and 19% of total tax revenues at the start of the episode.

The typical episode lasts 12 years. There is a small increase in the frequency of episodes in the recent period compared to the pre-1970 period (3 episodes for 100 observations versus 2 episodes for 100 observations prior to 1970) despite its much shorter time span. Episodes are also slightly deeper (bigger sizes spread out over shorter periods) since 1970. Turning to differences by income group at the start of the episode we see that poorer countries always experience deeper episodes. There are also much more likely to experience episodes since 1970: there are 0.3 episodes per 100 observations among HICs, 3.6 among MICs and 4.6 among LICs.

The last line of Table 3 presents the share of countries in which total tax revenues increase in the 3 years prior to the episode by at least as much as the size of the episode. We see that on average few countries -6.6% -preempt the loss in trade tax revenues (column 1). This share is much higher among countries that are HICs at the start of the episode; in particular the three rich countries which experience an episode after 1970 also experience increases in tax revenues prior to the episode that more than compensate for the loss in trade taxes.

Excluding these episodes from our sample does not change the overall picture in Table 3 (see web Appendix Table B.3).

Table 4 presents descriptive statistics for the 96 episodes that we can associate with a change in trade policy. These episodes are very similar to the average episode in Table 3.

On the whole the two tables indicate that countries are more likely to experience episodes of decrease in trade tax revenues at earlier stages of economic development and that this is particularly true since 1970.

Results: Fiscal Cost of Trade Liberalization

Table 5 presents our measure of the fiscal cost of trade liberalization. We find several patterns of interest.

First, many countries do not experience any fiscal cost of trade liberalization. The first line of the table presents the share of countries for which we do not observe any fall in total tax revenues at the start of an episode. In these countries trade tax revenues fall but domestic sources of tax revenues increase more than enough to compensate this fall. This occurs for nearly half of the episodes and more often in the pre-1970 period (55% of episodes, column 2) than in the recent period (44%, column 6). Developing countries are more likely than HICs to experience a fall in total tax revenues in the recent period (post-1970). None of the three HICs which experience a fall in tax revenues after 1970 experience such a fall in total tax revenues, while more than 50% of the MICs and 60% of the LICs do. Second, roughly one-fourth of the countries are never observed going back to their pre-episode level of tax revenues -we say that they experience no fiscal recovery. This is more likely in the recent period and again varies with economic development. All the HICs experience a fiscal recovery but more than a third of the developing countries for which the episode starts after 1970 do not. Third, the countries for which we observe both a fiscal cost and a fiscal recovery return to their pre-episode level of tax revenues faster since 1970 than before 1970 (third line). They do so on average 7 years after the start of the episode in the pre-1970 period and 4 years in the post-1970 period.

The fact that countries that experience episodes since 1970 are less likely to recover fiscally but recover faster when they do suggests that part of the differences across periods may be due to the fact that our data is truncated. We indeed observe countries for a smaller number of years in the post-1970 than in the pre-1970 period and may not have long enough time series after the most recent episodes to observe fiscal recoveries. Similarly, we could be observing less recovery in developing countries because data series are typically shorter for these countries than for HICs. We check that this is not what is driving our results. The fourth line in Table 5 indicates the number of years for which we observe countries in the data after the start of the episode. This number is only slightly higher in the post-than in the pre-1970 period. Results are moreover similar when we only consider countries which we observe for five, ten or twenty years after the start of the episode (last three lines). We always see countries recovering more in the pre-than in the post-1970 period; developing countries are always less likely to recover than HICs, especially in the post-1970 period.

Robustness Checks

Our definition of 'trade liberalization episodes' is overly sweeping. As explained above some of the episodes probably have little to do with trade liberalization policies; the evolution of total tax revenues after these episodes should not be interpreted as reflecting the fiscal cost of trade liberalization. Table 6 replicates the results in Table 5 for the sample of episodes that we can associate with a change in trade policy. The share of developing countries making a full fiscal recovery in the medium-run (10 or 20 years after the end of the episode) is slightly higher than in Table 5, in line with the idea that some of the other episodes may be due to external shocks that affect both domestic and trade collection negatively. The main patternlower likelihood of recovery in developing countries, particularly since 1970 -remains however similar.

The paper's web Appendix presents additional robustness checks on our measures of episodes of decreases in trade tax revenues and the fiscal cost of trade liberalization. Our results are unaffected if we only consider non pre-empted episodes (web Appendix Table B.9).11 Another potential concern is that the method we use to define episodes does not get rid of all noisy short-run variations in tax revenues, in which case some of our episodes are spurious, or gets rid of too much variation, leading us to exclude informative episodes.

We consider episodes defined using a higher (2 GDP points) threshold for the fall in trade tax revenues and check for the robustness of the results to the choice of filter by considering episodes obtained using different smoothing parameters for the HP filter (8.25, as in Ravn and Uhlig (2002) and 10, as in [START_REF] Hassler | The Swedish business cycle: stylized facts over 130 years[END_REF] and [START_REF] Baxter | Measuring Business Cycles: Approximate Band-Pass Filters For Economic Time Series[END_REF]). Another concern with the HP filter is its 'end-point bias' (see for example [START_REF] Baxter | Measuring Business Cycles: Approximate Band-Pass Filters For Economic Time Series[END_REF] as the last point of the series has an exaggerated impact on the trend.

We use the Christiano-Fitzgerald band-pass filter to check that this bias is not driving some of our results [START_REF] Christiano | The Band Pass Filter[END_REF]. Results are presented in Tables B.4 to B.7 and Tables B.10 to B.13 in the web Appendix. We obtain slightly more episodes (169) when using the Christiano-Fitzgerald method and slightly less when using higher values of the HP filter or a higher threshold for the definition of the episodes, as expected. The main patterns found in Tables 3 and5 are however unaffected; the results on the fiscal cost of trade liberalization are particularly robust to changes in the method used.

Finally, a large share of the economy in developing countries is informal [START_REF] Schneider | Shadow Economies: Size, Causes, and Consequences[END_REF]. If the informal sector of the economy is untaxed but partially captured in GDP data faster growth in the informal than in the formal sector would lead us to identify spurious episodes for which there is no fiscal recovery. We consider an alternative measure of episodes using data on tax revenues per capita to try to mitigate this concern: we say there is an episode when we observe a large fall in (smoothed) trade tax revenues per capita and look for fiscal recovery of the total tax revenues per capita variable. 12 The results are again very similar to those obtained using tax data normalized by GDP. The difference between the pre-and post-1970 periods is even stronger as all countries which experience an episode prior to 1970 are observed making a fiscal recovery at some point (web Appendix Tables B.8 and B.14).

Our findings therefore indicate that developing countries are more likely to experience a fiscal cost of trade liberalization, and experience it for longer, than both HICs today and HICs when they were at earlier stages of economic development. This suggests that the fall in tax ratios in these countries over the period 1970-2000 discussed in the introduction can at least partially be explained by the decrease in trade tax revenues. In the next section, we elaborate on the difference between today's developing countries and the historical experience of rich countries to discuss potential explanations for the fiscal cost of trade liberalization that we observe.

Discussion

Why are some countries able to recover the lost tax revenues from liberalizing trade through domestic sources of taxation when others are not? To answer this question one must first understand why trade taxes are such an important tax handle for countries at an early stage of economic development. We have seen that they represent more than 30% of total tax revenues in LICs in the 1970s as well as in today's HICs in the 1830s. The consensus in the literature is that while the Diamond-Mirrlees production efficiency theorem [START_REF] Diamond | Optimal Taxation and Public Production: I-Production Efficiency[END_REF] implies that taxes on international trade are inferior to most forms of domestic taxation (for a review see [START_REF] Dixit | Tax policy in open economies[END_REF], the former are easier to levy or more 'revenue-efficient', to follow the terminology in [START_REF] Best | Production vs Revenue Efficiency With Limited Tax Capacity: Theory and Evidence From Pakistan[END_REF]. Optimal tax theory therefore predicts that countries will only tax trade if they cannot raise sufficient revenues through taxes on domestic transactions. This may be the case in developing countries if economies at an early stage of development are intrinsically harder to tax -agriculture is hard to tax, and small firms are less likely to be tax compliant than large firms, as in [START_REF] Kleven | Why Can Modern Governments Tax So Much? An Agency Model of Firms as Fiscal Intermediaries[END_REF]. Alternatively, and following the concepts developed in Besley andPersson (2011, 2013), we can think that developing countries have less fiscal capacity and that less fiscal capacity is needed to levy trade taxes than broader-based domestic taxes: to levy tariffs governments only need to observe a few large transactions that are typically concentrated geographically.

These theories explain the tax transition observed in our data: as countries develop they decrease their revenues from taxes on trade and increase taxation from other sources. They are also consistent with the anecdotal historical evidence on rich countries which suggest that they gradually lowered tariffs once they had developed a fiscal administration which made it possible to raise tax revenues through other means [START_REF] Ardant | Histoire de l'Impot[END_REF]. As an example, consider one of the earliest episode we identify, in the United Kingdom in 1842. At this time over a third of the UK's tax revenues came from export and import duties. Prime minister Robert Peel implemented a large over-the-board decrease in tariffs, and financed the budget overhaul by re-introducing the income tax and mobilizing the country's modern tax bureaucracy built during the Napoleonic Wars. The extra tax revenue raised was more than expected, allowing for further tariff reforms starting in 1846, the famous repeal of the Corn Laws [START_REF] Bairoch | European Trade Policy, 1815 -1914[END_REF].

We observe immediate revenue recovery (no fiscal cost) for this episode.

These theories cannot on the other hand explain why we observe a fiscal cost of trade liberalization. On the contrary they predict that tax ratios will increase when tariffs decrease:

as countries become able to shift their tax mix away from inefficient taxes on trade the marginal cost of raising taxes falls leading to an increase in (optimal) tax ratios. To explain the decrease in tax ratios that we observe one has to assume that trade taxes decrease for exogenous -non fiscal -reasons. Governments may wish to enter trade agreements regardless of their potential fiscal costs, or may be pressured to do so by international institutions or large trade partners. [START_REF] Antrás | Foreign Influence and Welfare[END_REF] argue for example that powerful governments often succeed in changing the tariff policies of their smaller trade partners, a situation that may well characterize the experience of many developing countries since the 1970s. This would have lead them to decrease taxes on trade 'too early' from a fiscal perspective, i.e. before they were in a position to increase revenues from domestic sources of taxation. An alternative explanation is that what we observe is the consequence of an optimal policy change: governments in developing countries may have chosen to simultaneously open up to trade and lower their tax ratios. This seems consistent with the fact that many of our episodes occur during the 1980s and 1990s, a period during which many developing countries implemented structural stabilization plans, often under the auspices of the IMF. Liberalizing trade and lowering government expenditures were often seen as steps towards stabilizing the economy. Government policies that used tariff decreases as a way to both liberalize trade and lower tax ratios could explain the patterns we observe.

We do not attempt to discuss the potential net welfare gain or cost of trade liberalization here. On the one hand, given concerns about corruption levels in developing countries [START_REF] Olken | Corruption in Developing Countries[END_REF][START_REF] Banerjee | Corruption[END_REF] the decrease in tax revenues associated with trade liberalization may be optimal. On the other hand, public finance con-straints could explain persistent differences in growth rates across countries [START_REF] Aizenman | Globalization and Developing Countries -A Shrinking Tax Base?[END_REF]. We can however document the fiscal cost further by considering government expenditures. A fall in tax revenues can only be thought of as costly if it leads to a decrease in public spending and public spending has a positive impact on welfare. If it is compensated for by an increase in other sources of revenues -development aid or revenues from natural resources -the main potential reason to worry about the fiscal cost of trade liberalization becomes moot. 13 Using our data on government expenditures over GDP we consider whether (i) government expenditures fall at the start of each episode and (ii) if they do, the of years before government expenditures come back to their pre-episode level.

Table 7 presents our results regarding the expenditure cost of trade liberalization. We see that the shares of countries that experience an expenditure cost or are never observed to recover are slightly smaller than when we consider tax revenues in most income and period groups, particularly in LICs. This suggests that non-tax sources of public revenues were sometimes found to compensate for the fall in trade taxes. However, the general pattern remains the same: poorer countries are more likely than rich countries to experience a fiscal cost and less likely to recover in five, ten or twenty years. Trade liberalization episodes lead to a fall in government expenditures that is permanent in our data over 25% of the time in developing countries since 1970.

Conclusion

This paper shows that trade liberalization sometimes comes at a fiscal cost. Using a new panel dataset of tax revenues covering 130 developed and developing countries from 1792 to 2006, we characterize 140 episodes of decrease in trade tax revenues and consider the contemporary evolution of total tax revenues to investigate the potential fiscal cost of trade liberalization. We show that in the period since 1970 developing countries are more likely than rich countries to experience a fall in total tax revenues as they decrease trade taxes and less likely to recover the lost tax revenues through other sources of taxation. They are also more likely to experience a fall in total government expenditures. We observe similar episodes of decreases in trade tax revenues in today's rich countries when they were at earlier level of development in the 19th and early 20th centuries but find that they were less likely to experience a simultaneous decrease in total tax revenues than today's developing countries and that when they did this decrease was smaller and shorter-lived. Trade liberalization seems to have come at a larger fiscal cost in today's developing countries, possibly because they decreased taxes on trade before having developed tax administrations capable of taxing domestic transactions on a large scale.

The fiscal cost of opening up to trade experienced by developing countries could be eroding support for further trade liberalization. Trade taxes still represent 3.4% of GDP on average in 2000-2006 in the 30 low-income-countries in our sample, nearly one-fourth of total tax revenues. These are precisely the countries in which the international community calls for increases in domestic revenue mobilization [START_REF] Sachs | UN Millennium Development Project -Investing in Development : A Practical Plan to Achievet Goals[END_REF][START_REF] Gupta | Mobilizing Revenue[END_REF]OECD, 2010). Our findings suggest that increasing these countries' capacity to tax could weaken one of the reasons they are reluctant to embrace free trade by making governments less dependent on taxes on trade for public revenues.

HICs

MICs LICs 1 9 7 0 s 1 9 8 0 s 1 9 9 0 s 2 0 0 0 s 1 9 7 0 s 1 9 8 0 s 1 9 9 0 s 2 0 0 0 s 1 9 7 0 s 1 9 8 0 s 1 9 9 0 s 2 0 0 0 s ) 1972 1974 1976 1978 1980 1982 1984 1986 1988 1990 1992 1994 1996 1998 2000 2002 2004 Year Smoothed trade tax revenues Smoothed tax revenues

Trade tax revenues Tax revenues

Notes: The figure illustrates our method for constructing episodes of trade liberalization and the fiscal recovery variable. The vertical red line shows the start of the episode, the blue line its end and the green line the year of recovery. See the text for a description of the dataset used. Notes: Mean (standard error). The table presents descriptive statistics on our sample of 140 episodes of decrease in trade tax revenues. Total and trade tax revenues are measured at the start of the episode. The number of observations refers to the number of observations in our data set for the period and country income group under consideration. Column 1 presents results for the entire sample of episodes. In columns 2 to 5 (respectively 6 to 9), we present results considering only the period 1792-1969 (respectively 1970-2006). HICs (columns 3 and 7), MICs (columns 4 and 8) and LICs (columns 5 and 9) are defined using the country's income group at the start of the episode. Episodes are obtained on data smoothed using a HP filter with a smoothing parameter of 6.25. See the text for a description of the dataset and the method used to construct episodes. -1969 (respectively 1970-2006). HICs (columns 3 and 7), MICs (columns 4 and 8) and LICs (columns 5 and 9) are defined using the country income group at the start of the episode. Episodes are obtained on data smoothed using a HP filter with a smoothing parameter of 6.25. See the text for a description of the dataset and the methods used to construct episodes and determine potential causes of the episodes. to the number of observations in our data set for the period and country income group under consideration. Column 1 presents results for the entire sample of episodes. In columns 2 to 5 (respectively 6 to 9), we present results considering only the period 1792-1969 (respectively 1970-2006). HICs (columns 3 and 7), MICs (columns 4 and 8) and LICs (columns 5 and 9) are defined using the country income group at the start of the episode. Episodes are obtained on data smoothed using a HP filter with a smoothing parameter of 6.25. See the text for a description of the dataset and the method used to construct episodes. Notes: Mean (standard error). The table presents descriptive statistics on fiscal recovery for all episodes of decreases in trade tax revenues which we can associate with changes in trade policy. In columns 2 to 5 (respectively 6 to 9), we present results considering only the period 1792-1969 (respectively 1970-2006). HICs (columns 3 and 7), MICs (columns 4 and 8) and LICs (columns 5 and 9) are defined using the country income group at the start of the episode. Episodes are obtained on data smoothed using a HP filter with a smoothing parameter of 6.25. See the text for a description of the dataset and the methods used to construct episodes and determine potential causes of the episodes. Notes: Mean (standard error). The table presents descriptive statistics on expenditure recovery for all episodes of decreases in trade tax revenues. The number of observations refers to the number of observations in our data set for the period and country income group under consideration. Column 1 presents results for the entire sample of episodes.

In columns 2 to 5 (respectively 6 to 9), we present results considering only the period 1792-1969 (respectively 1970-2006). HICs (columns 3 and 7), MICs (columns 4 and 8) and LICs (columns 5 and 9) are defined using the country income group at the start of the episode. Episodes are obtained on data smoothed using a HP filter with a smoothing parameter of 6.25. See the text for a description of the dataset and the method used to construct episodes.

Figure 1 :

 1 Figure 1: Evolution of Total and Trade Tax Revenues since 1970 by Level of Development (a) Total Tax Revenues

  Each bar represents a mean taken over the 29 High Income Countries, 28 Middle Income Countries and 30 Low Income Countries for which data on total and trade tax revenues is available in all decades. Each country is given equal weight in the mean. Countries are categorized by their level of economic development in 2006, see the text for a description of the data used and the country income groups.

Figure 2 :

 2 Figure 2: Definition of Trade Liberalization Episodes and Fiscal Recovery: Example of Guatemala

Table 1 :

 1 Evolution of Tax Ratios, Tax Structures and GDP since 1830 by Level of Development Notes: Each value is a mean over a decade. The table presents descriptive statistics on total and trade tax revenues as a share of GDP and GDP per capita. Countries are categorized by their level of economic development in 2006, see the text for a description of the data and the country income groups. Each country is given equal weight in the mean. The number of observations in each decade

	HICs MICs LICs	(1) (2) (3) (4) (5) (6) (7) (8) (9)	Total tax Trade tax GDP Total tax Trade tax GDP Total tax Trade tax GDP	1830-1839 6.6 3.0 1674.5	1860-1869 9.1 1.4 2161.2	1890-1899 8.6 1.9 2334.6	1920-1929 12.7 2.3 3504.6 11.5 2.3 1658.5	1950-1959 16.9 2.0 5702.8 9.5 2.2 1734.2	15.6 5.9 970.3 1970-1979 22.2 1.6 10754.0 15.9 4.2 3286.7	14.0 3.1 928.9 2000-2006 27.6 0.6 16219.8 16.1 2.3 4069.0	from the top to bottom is (i) HICs: 3, 4,9, 12, 18, 25; (ii) MICs: 5, 12, 30, 43; (iii) LICs: 30, 40.

Table 2 :

 2 Evolution of Tax Ratios, Tax Structures and GDP since 1970 by Level of Development, Fixed Sample of Countries Notes: Each value is a mean over a decade. The sample consists of the 29 high-income countries, 28 middle-income countries and 30 low-income countries for which we have data in all decades. Countries are categorized by their level of economic development in 2006, see the text for a description of the country income groups. Each country is given equal weight in the mean.

	MICs LICs	(4) (5) (6) (7) (8) (9)	Total tax Trade tax GDP Total tax Trade tax GDP	16.3 4.4 3196.3 15.6 5.9 970.3	15.4 3.6 3346.2 15.1 5.3 946.5	15.1 2.8 3732.3 13.7 3.9 877.0	15.7 2.3 4115.9 14.9 3.4 928.3
		(3)	GDP	11016.0	12741.4	15430.2	18272.8
	HICs	(1) (2)	Total tax Trade tax	22.5 1.6	25.0 1.1	28.4 0.6	31.0 0.4
				1970-1979	1980-1989	1990-1999	2000-2006

Table 3 :

 3 Episodes of Decreases in Trade Tax Revenues

		(9)	LICs	3.8	(2.7)	12	(6)	16.9
	1792-1969 1970-2006	(1) (2) (3) (4) (5) (6) (7) (8)	Entire Sample All countries HICs MICs LICs All countries HICs MICs	3.2 2.3 1.9 2.4 2.3 3.5 2.1 3.1	(2.3) (1.3) (0.9) (1.4) (1.1) (2.5) (1.3) (2.2)	12 14 17 15 12 11 13 10	(6) (7) (8) (7) (5) (5) (3) (4)	16.9 14.7 19.7 15.2 11.1 17.7 24.7 18.2	(7.1) (6.8) (8.2) (6.8) (4.6) (7.0) (10.1) (6.7)
				Size of the episode (GDP points)		Length of the episode (years)		Total tax revenues (% GDP)

Table 4 :

 4 Episodes of Decreases in Trade Tax Revenues, Changes in Trade Policy Only Mean (standard error). The table presents descriptive statistics on the sample of episodes of decrease in trade tax revenues which we can associate with a change in trade policy. Total and trade tax revenues are measured at the start of the episode. Column 1 presents results for the entire sample of episodes. In columns 2 to 5 (respectively 6 to 9), we present results considering only the period 1792

	1792-1969 1970-2006	(1) (2) (3) (4) (5) (6) (7) (8) (9)	Entire Sample All countries HICs MICs LICs All countries HICs MICs LICs	3.2 2.4 1.4 2.6 2.2 3.4 2.4 3.1 3.8	(2.3) (1.4) (0.4) (1.5) (0.8) (2.5) (1.7) (2.1) (2.9)	12 15 18 15 12 11 14 10 12	(6) (7) (13) (7) (6) (6) (1) (4) (7)	16.7 14.2 16.7 15.2 10.1 17.6 20.3 17.8 17.3	(6.8) (7.0) (12.8) (6.8) (5.3) (6.6) (9.2) (6.1) (7.2)	5.4 4.0 2.6 4.1 3.9 5.9 2.4 5.1 7.0	(4.1) (1.6) (0.6) (1.8) (1.0) (4.7) (1.7) (2.7) (6.0)	96 27 2 19 6 69 2 34 33	80 20 0 15 5 60 2 29 29
				Size of the episode (GDP points)		Length of the episode (years)		Total tax revenues (% GDP)		Trade tax revenues (% GDP)		Number of episodes	Number of countries	Notes:

Table 5 :

 5 The Fiscal Cost of Trade Liberalization Mean (standard error). The table presents descriptive statistics on fiscal recovery for all episodes of decreases in trade tax revenues. The number of observations refers

	1792-1969 1970-2006	(1) (2) (3) (4) (5) (6) (7) (8) (9)	Entire Sample All countries HICs MICs LICs All countries HICs MICs LICs	47.1 55.3 50.0 64.0 33.3 44.1 100.0 47.7 38.2	(50.1) (50.4) (57.7) (49.0) (50.0) (49.9) (0.0) (50.5) (49.0)	27.9 7.9 0.0 8.0 11.1 35.3 0.0 34.1 38.2	(45.0) (27.3) (0.0) (27.7) (33.3) (48.0) (0.0) (47.9) (49.0)	5 7 6 4 16 4 1 4 4	(8) (10) (6) (5) (15) (6) (0) (7) (6)	21.1 40.0 . 17.0 86.0 19.6 . 16.3 21.9	(13.5) (41.9) (.) (18.4) (.) (8.0) (.) (9.2) (6.3)	49.3 56.8 50.0 66.7 33.3 46.5 100.0 48.8 41.8	(50.2) (50.2) (57.7) (48.2) (50.0) (50.1) (0.0) (50.6) (49.8)	56.6 64.9 75.0 75.0 33.3 53.3 100.0 52.8 50.9	(49.8) (48.4) (50.0) (44.2) (50.0) (50.2) (0.0) (50.6) (50.5)	66.7 84.4 100.0 95.2 42.9 55.1 100.0 60.0 51.5	(47.4) (36.9) (0.0) (21.8) (53.5) (50.3) (.) (50.7) (50.8)	140 38 4 25 9 102 3 44 55	110 28 2 20 6 82 3 36 43
				% Episodes with no fall in total tax revenues		% Episodes with no fiscal recovery		Actual recovery time (years)		Potential recovery time (years)		% Episodes with recovery under 5 years		% Episodes with recovery under 10 years		% Episodes with recovery under 20 years		Number of episodes	Number of countries	Notes:

Table 6 :

 6 The Fiscal cost of Trade liberalization, Changes in Trade Policy Only

	1970-2006
	1792-1969
	(1)

Table 7 :

 7 The Fiscal Cost of Trade Liberalization: Government Expenditures Recovery

	1792-1969 1970-2006	(1) (2) (3) (4) (5) (6) (7) (8) (9)	Entire Sample All countries HICs MICs LICs All countries HICs MICs LICs	55.7 68.4 75.0 76.0 44.4 51.0 66.7 47.7 52.7	(49.9) (47.1) (50.0) (43.6) (52.7) (50.2) (57.7) (50.5) (50.4)	23.57 2.63 0.00 4.00 0.00 31.37 0.00 43.18 23.64	(42.60) (16.22) (0.00) (20.00) (0.00) (46.63) (0.00) (50.11) (42.88)
				% Episodes with no fall in expenditures		% Episodes with no expenditure recovery	Actual recovery time (years)

This 'law' is named after German economist Adolph Wagner (1835-1917) who first analyzed the relationship between tax ratios and economic development.

See also[START_REF] De Paula | Value-Added Taxes, Chain Effects, and Informality[END_REF];[START_REF] Carrillo | Taxes, Prisons, and CFOs: The Effects of Increased Punishment on Corporate Tax Compliance in Ecuador[END_REF];[START_REF] Kumler | Enlisting Employees in Improving Payroll-Tax Compliance: Evidence from Mexico[END_REF];[START_REF] Gadenne | Tax Me, But Spend Wisely: Sources of Public Finance and Government Accountability[END_REF];[START_REF] Gerard | Informal Labor and the Cost of Social Programs: Evidence from 15 Years of Unemployment Insurance in Brazil[END_REF].

Formally, we say that there is continuity across sources if both sources have the same information for the years on which they overlap and/or there is less than a 1 GDP point difference in the total tax and trade tax series across sources. This threshold was choosen to ensure that no change in data sources could be mistaken for the start of an episode as defined below.

The World's Bank 1987 country classification uses a GDP concept that is slightly different from the one used in[START_REF] Maddison | Statistics on World Population, GDP and Per Capita GDP, 1-2008 AD[END_REF]. We choose the GDP per capita thresholds that most closely match the World Bank's classification in 1987 in our dataset.

Average tariff rates are calculated as the total revenue from import duties divided by the value of total imports in the same year.

This stylized fact was first documented by[START_REF] Hinrichs | A General Theory of Tax Structure Change during Economic Development[END_REF].

This corresponds to a value of 1600 for quarterly data.[START_REF] Ravn | On adjusting the Hodrick-Prescott filter for the frequency of observations[END_REF] show that the smoothing parameter should be adjusted according to the fourth power of a change in the frequency of observations.

More precisely, we associate an episode with a free-trade agreement if it occurs 3 years before or after the agreement. This is to take into account the fact that our smoothing method may lead us to measure the precise onset of the episode with error.

We take a conservative definition of 'non pre-empted episodes' and only keep episodes for which we have data 3 years prior to the episodes and there is no increase in tax revenues before the episode that is at least as big as the episode itself. This leaves us with 86 episodes.

We choose a 50% threshold to obtain a number of episodes that is similar (112) to the one obtained using our main definition.

This is particularly important in the post-1970 period given the importance that the 'aid for trade' paradigm has taken during this period. This paradigm advocates poverty alleviation via aid aimed at expanding export opportunities and domestic complementarities to trade (see for example[START_REF] Balat | Realizing the gains from trade: Export crops, marketing costs, and poverty[END_REF].


Yliès Falcone

Jean-Claude Fernandez

Laurent Mounier

Jean-Luc Richier
email: jean-luc.richier@imag.fr

{ylies Falcone

A Compositional Testing Framework Driven by Partial Specifications

We present a testing framework using a compositional approach to generate and execute test cases. Test cases are generated and combined with respect to a partial specification expressed as a set of requirements and elementary test cases. These approach and framework are supported by a prototype tool presented here. The framework is presented here in its LTL-like application, besides other specification formalisms can be added.

Introduction

Testing is a popular validation technique which purpose is essentially to find defects on a system implementation, either during its development, or once a final version has been completed. Therefore, and even if lots of work have already been carried out on this topic, improving the effectiveness of a testing phase while reducing its cost and time consumption remains a very important challenge, sustained by a strong industrial demand.

From a practical point of view, a test campaign consists in producing a test suite (test generation), and executing it on the target system (test execution). Automating test generation means deriving the test suite from some initial description of the system under test. The test suite consists in a set of test cases, where each test case is a set of interaction sequences to be executed by an external tester. Any execution of a test case should lead to a test verdict, indicating if the system succeeded or not on this particular test (or if the test was not conclusive).

The initial system description used to produce the test cases may be for instance the source code of the software, some hypothesis on the sets of inputs it may receive (user profiles), or some requirements on its expected properties at run-time (i.e., a characterization of its (in)-correct execution sequences). In this latter case, when the purpose of the test campaign is to check the correctness of some behavioral requirements, an interesting approach for automatic test generation is the so-called model-based testing technique. Model-based testing is rather successful in the communication protocol area, especially because it is able to cope with some non-determinism of the system under test. It has been implemented in several tools, see for example [START_REF] Hartman | Model based test generation tools survey[END_REF] for a survey. However, it suffers from some drawbacks that may prevent its use in other application areas. First of all, it strongly relies on the availability of a system specification, which is not always the case in practice. Moreover, when it exists, this specification should be complete enough to ensure some relevance of the test suite produced. Finally, it is likely the case that this specification cannot encompass all the implementation details, and is restricted to a given abstraction level. Therefore, to become executable, the test cases produced have to be refined into more concrete interaction sequences. Automating this process in the general case is still a challenging problem [START_REF] Van Der Bijl | Action refinement in conformance testing[END_REF], and most of the time, when performed by hand, the soundness of the result cannot be fully guaranteed.

We propose here an alternative approach to produce a test suite dedicated to the validation of behavioral requirements of a software (see Fig. 1). In this framework the requirements R are expressed by logical formulas ϕ built upon a set of (abstract) predicates P i describing (possibly non-atomic) operations performed on the system under test. A typical example of such requirements could be for instance a security policy, where the abstract predicates would denote some high-level operations like "user A is authenticated", or "message M has been corrupted". The approach we propose relies on the following consideration: a perfect knowledge of the implementation details is required to produce elementary test cases Tc i able to decide whether such predicates hold or not at some state of the software execution. Therefore, writing the test cases dedicated to these predicates should be left to the programmer (or tester) expertise when a detailed system specification is not available. However, correctly orchestrating the execution of these "basic test cases" and combining their results to deduce the validity of the overall logical formula is much easier to automate since it depends only of the semantics of the operators used in this formula. This step can therefore be produced by an automatic test generator, and this test generation can even be performed in a compositional way (on the structure of the logical formula). More precisely, from the formula ϕ, a test generation function automatically produces an (abstract) tester AT ϕ . This tester consists of a set of communicating test controllers, one for each operator appearing in ϕ. Thus, AT ϕ depends only on the structure of formula ϕ. AT ϕ is then instantiated using the elementary test cases Tc i to obtain a concrete tester T ϕ for the formula ϕ. Execution of this tester on the implementation I produces the final verdict.

We believe that this approach is general enough to be instantiated with several logic formalisms commonly used to express requirements on execution traces (e.g., extended regular expressions or linear temporal logics). This works extends some preliminary descriptions on this technique [START_REF] Darmaillacq | Test generation for network security rules[END_REF][START_REF] Falcone | A test calculus framework applied to network security policies[END_REF] in several directions: first we try to demonstrate that it is general enough to support several logical formalisms, then we apply it for the well-known LTL temporal logic, and finally we evaluate it on a small case study using a prototype tool under development.

In addition to the numerous works proposed in the context of model-based test generation for conformance testing, this work also takes credits from the community of run-time verification. In fact, one of the techniques commonly used in this area consists in generating a monitor able to check the correctness of an execution trace with respect to a given logical requirement (see for instance [START_REF] Havelund | Synthesizing monitors for safety properties[END_REF][START_REF] Chen | Checking and correcting behaviors of java programs at runtime with java-mop[END_REF] or [START_REF] Artho | Combining test case generation and runtime verification[END_REF] for a short survey). In practice, this technique needs to instrument the software under verification with a set of observation points to produce the traces to be verified by the monitor. This instrumentation should of course be correlated with the requirement to verify (i.e., the trace produced should contain enough information). In the approach proposed here, these instrumentation directives are replaced by the elementary test cases associated to each elementary predicates. The main difference is that these test cases are not restricted to pure observation actions, but they may also contain some active testing operations, like calling some methods, or communicating with some remote process to check the correctness of an abstract predicate.

The rest of the paper is organized as follows: Sect. 2 introduces the general approach, while Sect. 3 details its sound-proved application for a particular variant of the linear temporal logic LTL. Section 4 and 5 respectively describe the architecture of a prototype tool based on this framework, and its application on a small case study. The conclusion and perspectives of this work are given is Sect. 6.

The general approach

We describe here more formally the test generation approach sketched in the introduction. As it has been explained, this approach relies on the following steps:

generation of an abstract tester AT ϕ from a formal requirement ϕ; -instantiation of AT ϕ into a concrete tester A ϕ using the set of elementary testers associated to each atomic predicate of ϕ; -execution of T ϕ against the System Under Test (SUT) to obtain a test verdict.

Notations

A labelled transition system (LTS, for short) is a quadruplet S = (Q, A, T, q 0 ) where Q is a set of states, A a set of labels, T ⊆ Q × A × Q the transition relation and q 0 ∈ Q the initial state. We will denote by p a -→ T q (or simply p a -→ q) when (p, a, q) ∈ T . A finite execution sequence of S is a sequence (p i , a i , q i ) {0≤i≤m} where p 0 = q 0 and p i+1 = q i . For each finite execution sequence λ, the sequence of actions (a 0 , a 1 , . . . , a m ) is called a finite execution trace of S. We denote by Exec(S) the set of all finite execution traces of S. For an execution trace σ = (a 0 , a 1 , . . . , a m ), we denote by | σ | the length m + 1 of σ, by σ k...l the sub-sequence (a k , . . . , a l ) when 0 ≤ k ≤ l ≤ m, and by σ k... the sub-sequence (a k , . . . , a m ) when 0 ≤ k ≤ m. Finally, σ ↓X denotes the projection of σ on action set X. Namely,

σ ↓X = {a 0 •• • ••a m | ∀i•a i ∈ X ∧σ = w 0 •a 0 • • • w m •a m •w m+1 ∧w i ∈ (A \ X) * }.

Formal requirements

We assume in the following that the formal requirements ϕ we consider are expressed using a logic L . Formulas of L are built upon a finite set of n-ary operators F n and a finite set of abstract predicates {p 1 , p 2 , . . . , p n } as follows:

formula ::= F n (formula 1 , formula 2 , . . . , formula n ) | p i
We suppose that each formula of L is interpreted over a finite execution trace of a LTS S, and we say that S satisfies ϕ (we note S |= ϕ) iff all sequences of Exec(S) satisfy ϕ. Relation |= is supposed to be defined inductively on the syntax of L in the usual way: abstract predicates are interpreted over Exec(S), and the semantics of each operator F n (ϕ 1 , . . . , ϕ n ) is defined in terms of sets of execution traces satisfying respectively ϕ 1 , . . . , ϕ n .

Test process algebra

In order to outline the compositionality of our test generation technique, we express a tester using an algebraic notation. We recall here the dedicated "test process algebra" introduced in [START_REF] Falcone | A test calculus framework applied to network security policies[END_REF], but other existing process algebras could also be used.

Syntax.

Let Act be a set of actions, T be a set of types (with τ ∈ T ), Var a set of variables (with x ∈ Var ), and Val a set of values (union of values of types T ). We denote by expr τ (resp. x τ ) any expression (resp. variable) of type τ . In particular, we assume the existence of a special type called Verdict which associated values are {pass, f ail, inconc} and which is used to denote the verdicts produced during the test execution.The syntax of a test process t is given by the following grammar:

t ::= [b] γ • t | t + t | nil | recX t | X b ::= true | false | b ∨ b | b ∧ b | ¬b | expr τ = expr τ γ ::= x τ := expr τ | !c(expr τ ) | ?c(x τ )
In this grammar t denotes a basic tester (nil being the empty tester doing nothing), b a boolean expression, c a channel name, γ an action, • is the prefixing operator, + the choice operator, X a term variable, recX allows recursive process definition (with X a term variable) 3 . When the condition b is true, we abbreviate [true]γ by γ. Atomic actions performed by a basic tester are either internal assignments (x τ := expr τ ), value emissions (!c(expr τ )) or value receptions (?c(x τ )) over a channel c4 .

Semantics. We first give a semantics of basic testers (t) using rewriting rule between uninterpreted terms in a CCS-like style (see Fig. 2).

γ ∈ Act (•) [b]γ • t [b]γ t t[recX • t/X] [b]γ t γ ∈ Act (rec) recX • t [b]γ t γ ∈ Act t1 [b]γ t 1 (+) l t1 + t2 [b]γ t 1 γ ∈ Act t2 [b]γ t 2 (+) r t1 + t2 [b]γ t 2

Fig. 2. Rules for term rewriting

The semantics of a basic test process t is then given by means of a LTS S t = (Q t , A t , T t , q t 0 ) in the usual way: states Q t are "configurations" of the form (t, ρ), where t is a term and ρ : V ar → V al is an environment. States and transition of S t (relation -→) are the smallest sets defined by the rules given in Fig. 3 (using the auxiliary relation defined in Fig. 2). The initial state q t 0 of S is the configuration (t 0 , ρ 0 ), where ρ 0 maps all the variables to an undefined value. Finally, note that actions A t of S t are labelled either by internal assignments (x τ := v) or external emission (!c(v)). In the following we denote by A t ext ⊆ A t the external emissions and receptions performed by the LTS associated to a test process t.

Complex testers are obtained by parallel composition of test processes with synchronisation on a channel set cs (operator cs ), or using a so-called "joinexception" operator ( I ), allowing to interrupt a process on reception of a communication using the interruption channel set I. We note for ∅ and Act chan(s) all possible actions using a channel in the set s. To tackle with communication in our semantics, we give two sets of rules specifying how LTSs are composed relatively to the communication operators ( cs , I ). These rules aim to maintain asynchronous execution, communication by rendez-vous. Let

S t i = (Q t i , A t i , T t i , q t 0i
) be two LTSs modelling the behaviours of two processes t 1 and t 2 , we define the LTS S = (Q, A, T, q 0 ) modelling the behaviours of S

⊆ (Q t 1 ∪ {⊥}) × Q t 2
and the transition rules are given in Fig. 4.

ρ(exprτ ) = v t [b]xτ :=exprτ t ρ(b) = true (:=) (t, ρ) xτ :=v -→ (t , ρ[v/xτ ]) ρ(exprτ ) = v t [b]!c(exprτ ) t ρ(b) = true (!) (t, ρ) !c(v) -→ (t , ρ) v ∈ Dom(τ ) t [b]?c(xτ ) t ρ(b) = true (?) (t, ρ) !c(v) -→ (t, ρ[v/xτ ]) Fig. 3. Rules for environment modification p1 a -→ p 1 a / ∈ Act chan(cs) ( l cs ) (p1, p2) a -→ (p 1 , p2) p2 a -→ p 2 a / ∈ Act chan(cs) ( r cs ) (p1, p2) a -→ (p1, p 2 ) p1 a -→ p 1 p2 a -→ p 2 a ∈ Act chan(cs) ( cs) (p1, p2) a -→ (p 1 , p 2 ) p1 a -→ p 1 a / ∈ Act chan(I) ( I ) (p1, p2) a -→ (p 1 , p2) p2 a -→ p 2 a ∈ Act chan(I) ( I ) (p1, p2) a -→ (⊥, p 2 )

Test Generation

Principle. The test generation technique we propose aims to produce a tester process t ϕ associated to a formal requirement ϕ and it can be formalized by a function called GenTest in the rest of the paper (GenTest (ϕ) = t ϕ ). This generation step depends of course of the logical formalism under consideration, but it is compositionally defined in the following way:

a basic tester t pi is associated with each abstract predicate p i of ϕ;

-for each sub-formula φ = F n (φ 1 , • • • , φ n ) of ϕ, a test process t φ is produced,
where t φ is a parallel composition between test processes t φ1 , . . . , t φn and a test process F n called a test controller for operator F n .

The purpose of test controllers F n is both to schedule the test execution of the t φ k (starting, stopping or restarting their execution), and to combine their verdicts to produce the overall verdict associated to φ. As a result, the architecture of a tester t ϕ matches the abstract syntax tree corresponding to formula ϕ: leaves are basic tester processes corresponding to abstract predicates p i of ϕ, intermediate nodes are controllers associated with operators of ϕ.

Hypothesis. To allow interactions between the internal sub-processes of a tester t ϕ , we assume the following hypotheses:

Each tester sub-process t φ k (basic tester or controller) owns a special variable used to store its local verdict. This variable is supposed to be set to one of these values when the test execution terminates -its intuitive meaning is similar to the conformance testing case:

• pass means that the test execution of t φ k did not reveal any violation of the sub-formula associated to t φ k ; • f ail means that the test execution of t φ k did reveal a violation of the subformula associated to t φ k ; • inconc (inconclusive) means that the test execution of t φ k did not allow to conclude about the validity of the sub-formula associated to t φ k .

Each tester process t φ k (basic tester or controller) owns a set of four dedicated communication channels cs k = {c start k , c stop k , c loop k , c ver k } used respectively to start its execution, to stop it, to resume it from its initial state and to deliver a verdict. In the following, we denote by (cs, cs 1 , • • • , cs n ) each controller where cs is the channel set dedicated to the communication with the embracing controller whereas the (cs i ) are the channel sets dedicated to the communication with the sub-test processes. Finally, a "starter" process is also required to start the topmost controller associated to t and to read the verdict it delivered.

Each basic tester process t pi associated to an LTS S tp i is supposed to have a subset of actions A tp i ext ⊆ A tp i used to communicate with the SUT. Considering t = GenTest (ϕ), the set A t ext is defined as the union of the A

tp i
ext where p i is a basic predicate of ϕ.

Test generation function definition (GenTest).

GenT est can then be defined as follows using GT as an intermediate function:

GenTest (ϕ) def = GT (ϕ,

Test execution and test verdicts

As seen in the previous subsections, the semantics of a tester represented by a test process t is expressed by a LTS S t = (Q t , A t , T t , q t 0 ) where A t ext ⊆ A t denotes the external actions it may perform. Although the system under test I is not described by a formal model, its behaviour can also be expressed by a LTS S I = (Q I , A I , T I , q I 0 ). A test execution is a sequence of interactions (on A t ext ) between t and I in order to deliver a verdict indicating whether the test succeeded or not. We define here more precisely these notions of test execution and test verdict.

Formally speaking, a test execution of a test process t on a SUT I can be viewed as an execution trace of the parallel product ⊗ A t ext between LTSs S t and S I with synchronizations on actions of A t ext . This product is defined as follows:

S t ⊗ A t ext S I is the LTS (Q, A, T, q 0 ) where Q ⊆ Q t × Q I , A ⊆ A t ∪ A I , q 0 = (q t
0 , q I 0 ), and

T = {(p t , p I ) a -→ (q t , q I ) | (p t , a, q t ) ∈ T t ∧ (p I , a, q I ) ∈ T I ∧ a ∈ A t ext } ∪ {(p t , p I ) a -→ (q t , p I ) | (p t , a, q t ) ∈ T t ∧ a ∈ A t \ A t ext } ∪ {(p t , p I ) a -→ (p t , q I ) | (p I , a, q I ) ∈ T I ∧ a ∈ A I \ A t ext }. For any test execution σ ∈ Exec(S t ⊗ A t
ext S I ), we define the verdict function:

VExec(σ) = pass (resp. fail , inconc) iff σ = c start() • σ • c ver(pass) (resp. σ = c start() • σ • c ver(f ail), σ = c start() • σ • c ver(inconc)
) and c start (resp. c ver) is the starting (resp. the verdict) channel associated to the topmost controller of t.

Application to variant of LTL

This section presents an instantiation of the previous framework for a (non atomic) action-based version of LTL-X, the next-free variant of LTL [START_REF] Manna | Temporal verification of reactive systems: safety[END_REF].

The logic

Syntax. The syntax of a formula ϕ is given by the following grammar, where the atoms {p 1 , . . . , p n } are action predicates.

ϕ ::= ¬ ϕ | ϕ U ϕ | ϕ ∧ ϕ | p i
Semantics. Formulas ϕ are interpreted over the finite execution traces σ ∈ A * of a LTS. We introduce the following notations.

To each atomic predicate p i of ϕ we associate a subset of actions A pi and two subsets L pi and L pi of A * pi . Intuitively, A pi denotes the actions that influence the truth value of p i , and L pi (resp. L pi ) the set of finite execution traces satisfying (resp. non satisfying) p i . We suppose that the action sets A pi are such that {(A pi ) i } forms a partition of A, that for all i, j, L pi ∩ L pi = ∅ and (L pi ∪ L pi ) ∩ (L pj ∪ L pj ) = ∅. The sets of actions for a predicate are easily extended to sets of actions for a formula:

A ¬ϕ = A ϕ , A ϕ1∧ϕ2 = A ϕ1U ϕ2 = A ϕ1 ∪ A ϕ2 .
The truth value of a formula is given in a three-valued logic matching our notion of test verdicts: a formula ϕ can be evaluated to true on a trace σ (σ |= T ϕ), or it can be evaluated to false (σ |= F ϕ), or its evaluation may remain inconclusive (σ |= I ϕ).

The semantics for a formula ϕ is defined by three sets. The set of sequences that satisfy (resp. violate) the formula ϕ is noted [[ϕ]] T (resp. [[ϕ]] F ). We also note [[ϕ]] I the set of sequences for which the satisfaction remains inconclusive.

-[[p

i ]] T = {ω | ∃ ω , ω • ω = ω • ω ∧ ω ↓A p i ∈ L pi } [[p i ]] F = {ω | ∃ ω , ω • ω = ω • ω ∧ ω ↓A p i ∈ L pi } -[[¬ϕ]] T = [[ϕ]] F [[¬ϕ]] F = [[ϕ]] T -[[ϕ 1 ∧ ϕ 2 ]] T = {ω | ∃ ω , ω • ω = ω • ω ∧ ω ↓A ϕ 1 ∈ [[ϕ 1 ]] T ∧ ω ↓A ϕ 2 ∈ [[ϕ 2 ]] T } [[ϕ 1 ∧ ϕ 2 ]] F = {ω | ∃ ω , ω • ω = ω • ω ∧ ω ↓A ϕ 1 ∈ [[ϕ 1 ]] F ∨ ω ↓A ϕ 2 ∈ [[ϕ 2 ]] F } -[[ϕ 1 Uϕ 2 ]] T = {ω | ∃ ω 1 , . . . , ω n , ω • ω = ω 1 • • • ω n • ω ∧∀i < n • ω i↓ Aϕ 1 ∈ [[ϕ 1 ]] T ∧ ω n↓ Aϕ 2 ∈ [[ϕ 2 ]] T } [[ϕ 1 Uϕ 2 ]] F = {ω | ∃ ω 1 , . . . , ω n , ω • ω = ω 1 • • • ω n • ω ∧ " ∀i ≤ n•ωi ↓ Aϕ 2 ∈ [[ϕ2]] F ∨(∃l ≤ n•ω l↓ Aϕ 2 ∈ [[ϕ2]] T ∧∃k < l•ω k ↓ Aϕ 1 ∈ [[ϕ1]] F ) " } -[[ϕ]] I = A * \ ([[ϕ]] P ∪ [[ϕ]] F ) Finally we note σ |= T ϕ (resp. σ |= F ϕ, σ |= I ϕ) for σ ∈ [[ϕ]] T (resp. σ ∈ [[ϕ]] F ,σ ∈ [[ϕ]] I ).

Test generation

Following the structural test generation principle given in Sect. 2.4, it is possible to obtain a GenTest function for our LTL-like logic. The GenTest definition can be made explicit simply by giving controller definitions. So, we give a graphical description of each controller used by GenTest. To simplify the presentation, the stop transitions are not represented: the receptions all lead from each state of the controller to some "sink" state corresponding to the nil process, and emissions are sent by controllers to stop sub-tests when their execution is not needed anymore for the verdict computation.

The ¬({c start, c loop, c ver}, {c start , c loop , c ver }) controller is shown on

U (• • • ) = ( l (• • • ) r (• • • )) {r fail,l fail,r pass,l pass} m (• • • )
One could understand l and r as two sub-controllers in charge of communicating with the controlled tests that send relevant information to the "main" sub-controller m deciding the verdict. The reception of an inconclusive verdict from a sub-test process interrupts the controller which emits an inconclusive verdict (not represented on the figure). If no answer is received from the subprocesses after some finite amount of time, then the tester delivers its verdict (timeout transitions). For the sake of clarity we simplified the controller representation. First, we represent the emission of the controller verdict and the return to the initial state under a reception of a loop signal (?c loop()) by a state which name represents the value of the emitted verdict. Second, we do not represent inconc verdict, the controller propagates it.

Soundness proposition

We express that an abstract test case produced by the GenTest function is always sound, i.e. it delivers a pass (resp. fail ) verdict when it is executed on a SUT behavior I only if the formula used to generate it is satisfied (resp. violated) on I.

This proposition relies on one hypothesis, and two intermediate lemmas. Hypothesis 1 Each test case t pi associated to a predicate p i is strongly sound in the following sense:

∀σ ∈ Exec(t pi ⊗ Ap i I), VExec(σ) = pass ⇒ σ |= T p i ∀σ ∈ Exec(t pi ⊗ Ap i I), VExec(σ) = f ail ⇒ σ |= F p i
The lemmas state that the verdict computed by t ϕ on a sequence σ only depends on actions of σ belonging to A ϕ .

Lemma 1. All execution sequences with the same projection on a formula ϕ actions have the same satisfaction relation towards ϕ. That is:

∀σ, σ • σ ↓A ϕ = σ ↓A ϕ ⇒ (σ |= T ϕ ⇔ σ |= T ϕ) ∧ (σ |= F ϕ ⇔ σ |= F ϕ) Lemma 2.
For each formula ϕ, each sequence σ, the verdicts pass and fail of a sequence do not change if we project it on ϕ's actions. That is:

∀ϕ, ∀σ • σ |= T ϕ ⇒ σ ↓A ϕ |= T ϕ ∀ϕ, ∀σ • σ |= F ϕ ⇒ σ ↓A ϕ |= F ϕ
These lemmas come directly from the definition of our logic and the controllers used in GenTest. Now we can formulate the proposition. Theorem 1. Let ϕ be a formula, and t = GenTest(ϕ), S a LTS, σ ∈ Exec(t ⊗ Aϕ S) a test execution sequence, the proposition is:

V Exec(σ) = pass =⇒ σ |= T ϕ V Exec(σ) = f ail =⇒ σ |= F ϕ
Sketch of the soundness proof. The proof is done by structural induction on ϕ. We give the proof for two cases.

For the predicates The proof relies directly on predicate strong soundness (Hypothesis 1).

For the negation operator. Let suppose ϕ = ¬ϕ . We have to prove that:

∀σ ∈ Exec(GT (¬ϕ , L) ⊗ Aϕ I), VExec(σ) = pass ⇒ σ |= T ¬ϕ ∀σ ∈ Exec(GT (¬ϕ , L) ⊗ Aϕ I), VExec(σ) = f ail ⇒ σ |= F ¬ϕ Let σ ∈ Exec(GT (¬ϕ , L) ⊗ Aϕ I) suppose that VExec(σ) = pass. By definition of GT , GT (¬ϕ , L) = GT (ϕ , L ) L C ¬ (L, L )
Since controller C ¬ does not trigger the c loop transition of its subtest when it is used as a main tester process, execution sequence σ is necessarily in the form:

c start() • σ I • σ • σ I • ([x v = pass]x vg := f ail | [x v = f ail]x vg := pass | [x v = inconc]x vg := inconc) • σ I • c ver(x vg ) with σ ∈ Exec(GT (ϕ , L )⊗ A ϕ I)
σ ↓A ϕ = σ ↓A ϕ (∀ϕ, A ϕ = A ¬ϕ ) = σ ↓A ϕ (c start, σ I / ∈ A ϕ * ) So σ ↓A ϕ |= F ϕ . We conclude using the Lemma 1 that σ |= F ϕ that is σ |= T ¬ϕ . The proof for ∀σ ∈ Exec(GT (¬ϕ , L) ⊗ Aϕ I), VExec(σ) = f ail ⇒ σ |= F ¬ϕ is similar.
Others operators. Proofs for the other operators follow the same principle and can be found in [START_REF] Falcone | A partial specification driven compositional testing method and tool[END_REF].

j-POST

We now present j-POST, a prototype of a testing framework tool for the Java environment which follows our approach. We just describe an abstract view of the tool. Interested readers can refer to [START_REF] Falcone | A partial specification driven compositional testing method and tool[END_REF] which contains a more detailed description. j-POST contains a test generator using the compositional approach for Java, i.e. the tester is generated in Java, for a SUT written in the same language. An interface is provided for the user to write a library of elementary test cases from the SUT interface. Indeed, the interface defines a set of methods that can be called. Elementary test cases are terms of our test calculus which external actions correspond to these methods: execution of an external action on the tester leads to a complete execution of the method on the SUT (from the call to the return). An elementary test case execution on the tester leads to the execution of some methods in the SUT interface.

Afterwards, using our method, the tool transforms a specification in a given formalism in a abstract test case. Then it is combined with the library to provide an executable test case.

Synthesis algorithms of controlled tests for different formalisms have been defined and implemented. Two interfaces are provided to the user: a commandline mode and a graphic interface. A simplified version of the test generation and execution is depicted on Fig. 9. Elementary test cases library establishment. The SUT's architecture description provides the set of controllable and observable actions on the system. The user can compose them, with respect to the test calculus, and write new elementary test cases. Programming is eased by the abstraction furnished by the SUT interface.

Specification as a set of requirements. j-POST offers several formalisms to express requirements on the system.

• Temporal logics. Temporal logics [START_REF] Manna | Temporal verification of reactive systems: safety[END_REF] are frequently used to express specification for reactive systems. Their use has proved to be useful and appreciated for system verification. Our case studies have shown that many concepts in security policies are in the scope of these logics. • Regular Expression. Regular expressions [START_REF] Kleene | Representation of events in nerve nets and finite automata[END_REF] allows to define behaviour schemes expressed on a system traces. They are commonly used and wellunderstood by engineers for their practical aspect.

Test of a system. j-POST translates the specification into abstract test cases following the specification formula structure. Depending on the used specification formalism and the expressed requirement, the tool generates a test architecture whose test cases are coming from the controller library in accordance with Gen-Test. An execution engine is also generated. So, the generated tester can execute different test cases translated into a unique representation formalism on the test calculus engine. The initial SUT is also modified by adding a stub to communicate with the tester. This component provides means to launch method calls on the reception of specific signals. Thus, abstract test cases executing on the tester guide concrete test cases execution on the modified SUT. Communication between tester and SUT is done using the Java-RMI mechanism as we plan to support distributed SUT in a future evolution of our tool.

Case study

We present a case study illustrating the approach presented above. From some credit card security documents [START_REF] Mantel | Guideline for the development and evaluation of formal security policy models in the scope of itsec and common criteria[END_REF], we established a security policy and a credit card model. We applied our method with the security policy as a partial specification and the executable credit card model as a SUT. The credit card model and part of its security policy are overviewed here.

The card. The architecture of the credit card is presented on Fig. 1. After three failed authentications, the card is blocked, i.e. no action is permitted anymore. 2. If the card is suddenly removed the number of remaining authentications tries is set to 0. 3. No action is permitted without an identification.

For example one could see the first property formalised in our logic as several rules, one for each possible action: try 3 authentications(all f ailed) =⇒ action(blocked)

The third one could be reasonably understood as:

action(blocked) U authentication(success)

With this formalisation, these properties were tested with test cases that use elementary combinations of card interface actions. For example we wrote an abstract test case leading to three failed authentications using actions provide pin and init session.

Conclusion

In this work we have proposed a testing framework allowing to produce and execute test cases from a partial specification of the system under test. The approach we follow consists in generating the test cases from some high-level requirements on the expected system behaviour (expressed in a trace-based temporal logic), assuming that a concrete elementary tester is provided for each abstract predicate used in these requirements. This "partial specification" plays a similar role to the instrumentation directives currently used in run-time verification techniques, and we believe that they are easier to obtain in a realistic context than a complete operational specification. Furthermore, we have illustrated how this approach could be instantiated on a particular logic (an action-based variant of LTL-X), while showing that it is general enough to be applied to other similar trace-based logics. Finally, a prototype tool implementing this framework is available and preliminary experiments have been performed on a small case study.

Our main objective is now to extend this prototype in order to deal with larger examples. A promising direction is to investigate how the so-called MOP technology [START_REF] Chen | Checking and correcting behaviors of java programs at runtime with java-mop[END_REF] could be used as an implementation platform. In particular, it already offers useful facilities to translate high-level requirements (expressed in various logics) into (passive) observers, and to monitor the behaviour of a program under test using these monitors. A possible extension would then be to replace these observers by our active basic testers (using the aspect programming techniques supported by MOP).

Fig. 1 .

 1 Fig. 1. Test generation overview

Fig. 4 .

 4 Fig. 4. LTS composition related to cs and I

  cs) {c start,c ver} (!c start()•?c ver(x) • nil) where cs is the set {c start, c stop, c loop, c ver} of channel names associated to tϕ. GT (pi, cs) def = T est(tp i , cs) GT (F n (φ1, . . . , φn), cs) def = (GT (φ1, cs1) • • • GT (φn, csn)) cs F n (cs, cs1, . . . , csn) where cs1, . . . , csn are sets of fresh channel names and cs = cs1 ∪ • • • ∪ csn. T est(tp, {c start, c stop, c loop, c ver}) def = recX (?c start() • tp•!c ver(ver)•?c loop() • X) {c stop} (?c stop() • nil)

Fig. 5 .Fig. 5 .Fig. 6 .

 556 Fig. 5. The ¬ controller

Fig. 7 .Fig. 8 .

 78 Fig. 7. The U controller, the m part

  , σ I denoting SUT's actions, and ω • (a | b) • ω denoting the sequences ω • a • ω and ω • b • ω . As the controller emits a pass verdict (!c ver(x vg ) with x vg evaluated to pass in the C ¬ 's environment) it means that it necessarily received a f ail verdict ([x v = f ail]x vg := pass) on c ver from the sub-test corresponding to GT (ϕ , L ). So we have σ ∈ Exec(GT (ϕ , L ) ⊗ A ϕ I) and VExec(σ ) = f ail. The induction hypothesis implies that σ |= F ϕ . The Lemma 2 gives that σ ↓A ϕ |= F ϕ . And we have:

Fig. 9 .

 9 Fig. 9. Simplified working principle

  [START_REF] Kleene | Representation of events in nerve nets and finite automata[END_REF]. The interface is modeled by the Device component, corresponding to the possible action set on the card. Several banking operations are proposed, e.g. provide pin, change pin, init session, transaction, close session. Choice was made to use a Java interface to model the banking application one. The Device component interacts with a Memory Abstraction component providing, as its name indicates, some basic operations on the memory's areas. The Memory is just the credit card memory represented as a fixed size integer array.The security policy. Our study allowed us to extract several security requirement specific to the credit card security domain. These requirements concerned several specification formalisms: regular expressions, and temporal logics. Some examples of properties that we were able to test can be expressed at an informal level:

		Memory Abstraction
	Observations
	Controls	Device	Memory
	Fig. 10. The credit card architecture

We will only consider ground terms: each occurrence of X is bound to recX.

To simplify the calculus, we supposed that all channels exchange one value. In the testers, we also use "synchronisation channels", without exchanged argument, as a straightforward extension.

Acknowledgement. The authors thank the referees for their helpful remarks.