Patrick Guillaumont

Frédéric Puech

Macro

Keywords:

published or not. The documents may come

Introduction

Relying on samples taken from developing and developed countries, several recent papers, such as those by [START_REF] Fajnzylber | What Causes Violent Crime?[END_REF], [START_REF] Soares | Development, Crime and Punishment: Accounting for the International Differences in Crime Rates[END_REF] and [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF][START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF], have emphasized the influence of macro-economic variables on crime. Those studies highlight the impact of the average level of income and of its growth rate. But none of them consider the impact of its instability. This paper argues that the factors corresponding to economic shocks or macro-economic instability have a significant and robust influence on crime. It suggests that this influence comes from disappointed anticipations, formed during periods of rapid increase of income, which, to some extent, generates frustration and possibly crime. It also suggests that illegal activities are used by some agents to compensate their loss of income and, in this way, smooth their consumption. It mainly deals with the direct effect of instability on crime.

Nevertheless, since macro instability reduces growth, as it has been largely substantiated in literature, and growth has been found to have a negative impact on crime, it can also be supposed to have an indirect effect on crime through the growth rate.

We tested our hypothesis of a direct effect of macro instability for two kinds of crime: the utmost crime against persons, homicide, and crime against property, robbery. The samples are those used by [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF] for homicide and [START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF] for robbery.

Those samples both cover a set of developed and developing countries during the 1980-97 period and are much larger than those previously used by [START_REF] Fajnzylber | What Causes Violent Crime?[END_REF].

Results support the hypothesis that income instability has a significant influence upon crime. They are more outstanding for homicide than for robbery.

The remainder of this paper is as follows. Section 2 presents the conceptual framework for identifying variables usually considered as determinants of crime and for discussing the effects of instability and volatility on crime. Section 3 presents the data and samples and explains how instability indicators are built. Results are analyzed in section 4. Section 5 concludes.

Conceptual framework

"Traditional" variables

According to the economic theory of crime initiated by [START_REF] Becker | Crime and Punishment: an Economic Approach[END_REF] and [START_REF] Ehrlich | Participation in Illegitimate Activities: a Theoretical and Empirical Investigation[END_REF], criminals, like other individuals, are supposed to maximize their expected utility and react to incentives. Crime is seen as a consequence of a rational allocation of time between legal and illegal activities. In other words, each agent compares his or her expected earnings in the legal and illegal sectors, and becomes a criminal if illegal income is higher.

This choice is largely influenced by deterrence or, more precisely, by the probability of apprehension and the size of punishment: the number of crimes committed decreases with the importance of deterrence. As a consequence, a large part of the literature dealing with determinants of crime focuses on the effect of deterrence1 . This literature also tries to identify variables which are considered as "traditional" determinants of crime, even if their effect is not always clear. This is particularly the case for the average level of income. On the one hand, a higher average income results in more opportunities in the legal labor market thus leading to a reduction in crime against property. On the other hand, it also increases opportunities for criminals since there are more goods to steal. Similar arguments also apply to income growth so that the overall effect of these two variables is undetermined. Another hypothesis recently advanced by [START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF], concerns the effect of income inequality upon crime. Crime against property may be seen as an attempt by the poorest to reduce the gap between their own income and the income of the richer parts of the population. Furthermore, income inequality reduces the opportunity cost of crime, at least for the poor. Finally, relative deprivation induced by inequality generates frustration and increases violence. As a consequence, a positive effect of inequality on crime is expected. However, this effect is not always seen as significant in empirical studies, particularly at a macro-economic level.

Several explanations have been given for this result, including a lack of data for a large number of countries and a lack of temporal variation of the variable used (generally, the

Gini index).

The theoretical model developed by [START_REF] Becker | Crime and Punishment: an Economic Approach[END_REF] is possibly not adapted for explaining violent crime without any economic concern since it is unlikely that an individual makes a rational analysis before committing an assault or a murder. Further additional theoretical background is needed to explain this kind of crime. [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF] singles out three theories to explain violence. Firstly, the modernization theory suggests that the process of modernization in a given country increases violence because previous social control mechanisms are destroyed, in partly due to urbanization: the process leads to an alienation of individuals (particularly those who were unable to adapt to this new type of society), and to an anomie situation (absence of norms), which can lead to an increase of violence. Secondly, the opportunity theory suggests that crime increases if the opportunities for criminals increase: these opportunities can be pecuniary as well as social and demographic, justifying the use of population density or the percentage of young males in the population as "pro-crime" variables. The third theory, quoted by [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF], is cultural: crime varies following cultural differences amongst countries (or amongst groups within a country). Hereafter we will refer to this classification when analyzing the impact of instability on crime.

The effect of macro-economic instability

According to the modernization theory, individuals' propensity to violence can be seen to increase in a changing economic and social environment, firstly, because social control mechanisms are less efficient and secondly because individuals who are incapable of adapting become frustrated. Macro-economic instability can thus influence crime through this channel: instability warps anticipations, especially if it occurs due to macro-economic shocks. If a country benefits from good economic perspectives, agents will have optimistic expectations. Then, if a negative shock occurs, individuals will have to give up their aspirations. Not only are anticipations rendered more difficult, thus generating deception, but, as the newly created needs cannot be satisfied, frustration increases and is more likely to be translated into violence.

Moreover, instability reduces the opportunity costs of crime against property by reducing opportunities in the legal sector. The wage the criminal could have earned by working instead of committing a crime is uncertain if there is instability, thus rendering illegal activities relatively less risky than what they would be in a situation without instability.

This argument is rather similar to the one used to link unemployment to crime: the fewer opportunities there are in the legal labor market, the more attractive illegal activities become, especially if they become regular (as in organized crime for example), enabling the criminal to smooth his income and consumption. From this point of view, crime can be considered as a kind of diversification of activities in order to protect oneself against climate or price shocks. Even if opportunities for criminals are also more uncertain, it seems reasonable to assume that macro-economic instability increases crime against property since it lowers its opportunity costs.

To some extent, instability can also increase homicides, since it can be seen as an "efficient" way to reallocate resources after a shock. [START_REF] Miguel | Poverty and Witch Killing[END_REF] discovered that murders of elderly women in rural Tanzania increase after extreme rainfalls (a negative income shock leading to food shortage), the justification for these murders being that these women were witches. In another paper, [START_REF] Miguel | Economic Shocks and Civil Conflict: an Instrumental Variables Approach[END_REF] find that income shock (instrumented by rainfall variations) increases violence in Africa by raising the probability of civil war.

We should also keep in mind the indirect effect of instability on crime, through the growth rate. A lot of studies have estimated the impact of export instability (or other exogenous sources of instability) or of growth volatility on average growth in developing countries (see [START_REF] Ramey | Cross-Country Evidence on the Link Between Volatility and Growth[END_REF][START_REF] Guillaumont | How Instability Lowers African Growth[END_REF][START_REF] Hnatkovska | Volatility and Growth[END_REF][START_REF] Guillaumont | Macroeconomic Vulnerability and Aid Response[END_REF]. Indeed, instability by generating risk may increase precautionary savings. But more significantly, it slows down, through several channels, productivity improvement, innovation and finally the growth rate. If average growth (and thus the level of income) has a negative effect upon crime, which is often assumed, then instability, by reducing average growth, also indirectly increases crime. Since in our regressions, where crime is explained by both the average level of income per capita and the growth rate, this effect is already captured, we must not forget that our analysis is focused on direct effects, i.e. those which do not go through the level or the growth of income.

3 The data

Explained variables

Macro-economic analysis of crime suffered for a long time from the lack of quality data, in particular because the legal definition of crime differed among countries. The United Nations' World Crime Surveys (WCS hereafter) filled this void. This dataset is built upon surveys from governments, conducted in several waves by the United Nations since 1970, and deals with the judiciary system as a whole (number of crimes committed, police size, justice organization). However, they are official crime data, well-known to under-estimate the true crime rates as not every crime is reported to the police. Moreover, they are issued from surveys transmitted to governments, which implies firstly, that countries can choose not to answer, and secondly, that the data cannot be verified.

It is therefore better, as much as possible, to use other sources. Firstly, one can use data issued from the World Health Organization (WHO). These data contain, for every country and every year, the number of deceases classified depending on the cause of the death, with a specific category for homicide. Since these data come from the health administration of each country, it is, a priori, more reliable than WCS data. Finally, data for crime against persons as well as crime against property can be obtained from Interpol. These data are collected directly from the police, which reduces the risk of manipulation by the government or the likelihood of errors (even if WCS data more than likely come from the same source). Moreover, Interpol data cover a larger number of countries than the WCS and gives a more representative sample. We used the databases of [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF] for homicide and of [START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF] for robbery 2 , which correspond to two panels of developing and developed countries for six 3-year periods covering the 1980-97 period. Homicide rates are taken mainly, and in priority, from WHO data, considered as the more reliable source. The sample is completed by Interpol data, where they exist. Robbery rates come exclusively from Interpol. We thus have a sample of 132 countries for homicide and 87 for robbery, of which a large number are developing countries. This is one of the advantages of the dataset used by

Neumayer compared to the one used by [START_REF] Fajnzylber | What Causes Violent Crime?[END_REF], who use WCS data and thus get a sample of only 45 countries for homicide and 34 for robbery. Furthermore, a large part of the observations in their samples covers developed countries.

Traditional determinants

The baseline model includes economic, social, demographic and deterrence variables in order to take into account the main determinants of violent crime. Economic variables are the level of income, measured by the GDP per capita, the level of inequality (measured by the Gini index) and the GDP growth rate, as in [START_REF] Fajnzylber | What Causes Violent Crime?[END_REF]. Concerning the robbery rate, we are followed [START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF] and also introduced the squared GDP per capita in order to take into account a possible non-linear relation between average income and crime against property: At first, the number of robberies increases as average income increases (because opportunities increase) but, as everybody gets richer on average (whatever the distribution of wealth), incitation to commit a robbery decreases. In other words, we can assume that there exists a Kuznets curve for robbery.

Social variables in the baseline model are the literacy rate as well as female labor force participation. The latter is introduced as a proxy for the weakness of social linkage; with the underlying assumption that a higher female labor force participation means lower parental control, which tends to reduce social linkage between individuals. According to [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF], this variable measures the extent to which the traditional social structure which is dominated by males in numerous countries, remains in place and is thus a way to indirectly measure anomie. Some studies prefer to use the divorce rate and some others, such as [START_REF] Glaeser | Why Is There More Crime in Cities?[END_REF], use the percentage of female-headed households.

The two demographic variables most often used are the percentage of young males in the population and the urban rate. Young males are perceived as having a higher tendency to be violent than the rest of population. However, we must remark that, unless we assume there is a significant difference between male and female populations, this variable measures in fact the youth of the population. The urban rate is expected to have a positive impact on both homicide and robbery rates for three reasons, emphasized by [START_REF] Glaeser | Why Is There More Crime in Cities?[END_REF]. Firstly, urbanization goes hand in hand with a high population density, which means more possibilities for criminals to hide. Secondly, the number of policemen per capita is smaller in cities, reducing the probability of apprehension. Lastly, concerning crime against property specifically, the high population density due to urbanization means a lot of opportunities (and high potential of spoils) as well as a low cost of crime (especially in terms of the distance to be covered).

Finally, we introduced a dummy variable indicating whether the death penalty exists in each country and for each period in order to take into account the effect of deterrence on crime. Variables generally used to measure deterrence, such as the number of policemen per capita or the amount of police expenditure, suffer from an endogenous bias. If it is possible to efficiently and elegantly overcome this problem when working on micro-data (as carried out by [START_REF] Levitt | Using Electoral Cycles in Police Hiring to Estimate the Effect of Police on Crime[END_REF], it is much more difficult to find an exogenous source of variation for that kind of variable at the macro-economic level. This is why we chose to use the death penalty, which is, a priori, the more exogenous police variable at this level: the existence of the death penalty in a country is mainly the consequence of a political choice and is relatively independent from crime. Furthermore, the use of this variable seems particularly relevant in the case of homicide, since it is generally used to punish that kind of crime. Finally, this variable also has the advantage of not suffering from any measurement error since the existence of the death penalty in a country is clearly known.

Macro-economic instability variables

We distinguished two kinds of variables. The first one tried to measure exogenous sources of macro-economic instability. The second one dealt with growth rate volatility, which depends both on structural factors and on economic policy.

We considered two kinds of exogenous shocks which can lead to macro-economic instability. The first one comes from external trade fluctuations and is measured by calculating the instability of exports in constant dollars, weighted by the share of exports in GDP.

The second one is bound to climate and is measured by the instability of agricultural added value in constant dollars (also weighted by the share of agriculture in GDP). The use of these variables seems relevant since our sample is taken from a lot of developing countries, which are particularly vulnerable to these kinds of shocks. It should be recalled that these two instabilities (not weighted) are among the components of the economic vulnerability index (EVI) used by the United Nations for identifying the least developed countries (United Nations 2000). We also built a similar indicator for the instability of GDP per capita.

These instability measures are calculated as indices of the deviation of each variable from a mixed trend, both deterministic and stochastic. We began by running the following regression:

y i,t = αt + βy i,t-1 + c + ǫ i,t (1)
where y i,t is the variable considered (agricultural value added, exports or GDP per capita) for each country i and each year t. In this equation, we considered a ten-year trend. We then computed the instability index as follows:

IN S i,t = 100. T t y i,t -ŷ i,t ŷi,t 2 N (2)
where ŷi,t is the value of y i,t as predicted by equation 1, T is the length of the period considered and N is the number of observations for the period. The indices are computed for the last year of each three-year period covered by the sample (1982, 1985, 1988, 1991, 1994 and 1997). In order to find which is the most relevant length of the period of instability leading to crime, several indices were computed, referring to instability respectively during the four, five, six, eight and ten years preceding each year considered: we assume the relevant length can be different for homicide and for robbery.

To check whether our results are sensitive to the instability measurement, we also built, for each of the three variables used, an instability index with regards to a trend measured by the [START_REF] Hodrick | Postwar U.S. Business Cycles: An Empirical Investigation[END_REF] filter. Instead of smoothing each variable with a simple linear regression (like the one proposed in equation 1), we used this method, which allows for a better smoothing of the series. We then computed an instability index following the formula presented in equation 2 where ŷi,t corresponds to the smoothed variable (what Hodrick & Prescott call the growth of the variable) and (y i,tŷi,t ) corresponds to "cyclical" variations.

We also computed a variable measuring growth volatility, which is, as used by [START_REF] Ramey | Cross-Country Evidence on the Link Between Volatility and Growth[END_REF], the variance of the growth rate of GDP. Similarly to our work on instability, this variance was computed for the last year of each three-year period on the four, five, six, eight and ten preceding years.

Finally, the effect of instability may of course differ according to the institutional environment and be a stronger effect the weaker institutions are. Similarly, it may be expected to be lower in the OECD than in developing countries. Since this hypothesis can only be tested using an OECD dummy variable, and since regressions are estimated by using fixed effects, this dummy variable is introduced only as a multiplicative factor of instability. In order to test more specifically the hypothesis that the quality of institutions has an impact, we also introduced in regressions the composite international country risk guide (ICRG) index, both additively and as a multiplicative factor of instability.

Results

Basic results are presented in Table 1 for homicide and Table 2 for robbery. We followed [START_REF] Neumayer | Good Policy Can Lower Violent Crime: Evidence from a Cross-National Panel of Homicide Rates, 1980-97[END_REF][START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF]) and used the fixed-effects estimator. We did not use the GMM estimator (used by [START_REF] Fajnzylber | What Causes Violent Crime?[END_REF], even though it makes it possible to take into account criminal inertia because it is not adapted to the structure and availability of our data: this estimator actually requires the presence, for each country, of at least three consecutive periods, but the analysis of data reveals that only the developed countries and some intermediary-level income countries (most of them from Latin America) meet this requirement. Using GMM would lead to a significant loss of information and a type of selection bias as only the countries which have a reliable and efficient statistical system (as well as a sufficient political control to make the government publish the statistics) would be included in the sample. Moreover, in each and every regressions, we corrected, using a bootstrap technique, the standard errors associated with instability variables since they are generated variables leading to bias in the second-step estimation.

We carried out similar work for the two kinds of crime: column (1) of each table is the baseline model, without any instability or volatility variable. This estimate includes both the Gini index and literacy rate, which are further dropped because these two variables do not have any significant effect and generate an important loss of observations. The Gini index, which comes from the WIDER database, is a very incomplete series (especially for developing countries) and has a small time variation. It is thus likely that the effect of this variable will be taken into account by the cross-section fixed-effects or that unobservable factors will have a simultaneous impact on both income inequality and crime, as suggested by [START_REF] Bourguignon | Crime as a Social Cost of Poverty and Inequality: A Review Focusing on Developing Countries[END_REF]. For this reason, [START_REF] Neumayer | Inequality and Violent Crime: Evidence from Data on Robbery and Violent Theft[END_REF] argues that the macro-economic level may not be the most relevant one to study the link between inequality and crime.

Literacy rate, taken from the World Development Indicators of the World Bank has the inverse bias since indicators for this variable do not contain any data for developed countries and also evidence slow variations over time. Therefore, we decided to drop these two variables in the following regressions.

<Table 1 here> <Table 2 here>

According to column (2) of Table 1, GDP per capita level and growth rate have sig-nificant negative effects on the homicide rate and the percentage of young males in the population has a significant positive effect, as expected. However, the other control variables do not have any significant effect and the overall explanation power of the model is rather weak (R2 around 0.15). This result, which suggests that most homicides remain unexplained, is relatively frequent in literature [START_REF] Fajnzylber | Crime and Victimization: an Economic Perspective[END_REF]: even if violence has some objective determinants, it remains mostly a random phenomenon. This argument confirmed by the fact that the model is much more efficient for explaining the robbery rate (column (2) of Table 2). As we expected, the death penalty is the only insignificant variable, since it is normally not a sentence for robbery, and also because this variable does not vary enough over time to have any effect. It should also be noted that the urbanization rate has a surprisingly negative effect on robbery. Two explanations can be brought forward. Firstly, in a study of crime in Madagascar, [START_REF] Fafchamps | Crime, Isolation, and Law Enforcement[END_REF] found that it mainly occurs in the rural parts of the country and consists of cattle theft. Even if this study deals with only one country with specific characteristics, its results suggest the presence of a specific rural insecurity in developing countries. Furthermore, during the period considered (1980-97), countries with the highest urbanization level relatively to income were the developed ones, which also have smaller crime rates than developing countries.

The following columns show the results of estimates including instability variables.

Columns (3) and (4) include the instability of agricultural added value and the instability of exports for each kind of crime, column (4) presents results where instability is computed when the trend is measured using the Hodrick & Prescott filter. These regressions were run on a limited sample due to the lower number of observations for these two kinds of instability. Finally, columns (5) to (7) include the instability of GDP per capita and the growth rate volatility.

Column (3) of Table 1 suggests a significantly positive and equally important effect of both agricultural added value and exports instabilities, even if it is rather small: a 1% increase in agricultural added value instability increases the homicide rate by 0.107% (0.11% for exports instability). Table 1 also shows a significantly positive effect of both instability of GDP per capita and volatility of growth. If we turn to table 2, we can see that these two variables also have a significantly positive effect on robbery, which is not the case for the instability of agricultural added value and of exports. It seems that instability of income and growth volatility are more likely to be a factor of income smoothing (in an illegal than exogenous shocks.

Let us now consider the evolution of the coefficients associated with instability when the period over which instability is taken into account varies. Results are presented in Table 3 for homicide and 4 for robbery. Coefficients of instability variables presented in these tables come from regressions identical to those presented in tables 1 and 2 respectively, with the "length" of instability varying. As such, coefficients presented in tables 3 and 4 when instability is computed on 8 years are identical to those presented in tables 1 and 2. Table 3 suggests that the effect of instability on homicide, however it is measured, decreases with the length of instability considered, even if it is always significant. Table 4 suggests the opposite behavior for the elasticity of robbery due to instability, namely this elasticity increases when the period considered for measuring instability decreases, though it is always insignificant for the agricultural added value and export instability. In other words, robbery is more an immediate response to instability, suggesting that it is actually used by some people to compensate for their income loss due to negative shocks and therefore as a mean of smoothing their consumption. Homicide, on the other hand, is a response to both short-term and long-term instability, which is consistent with the hypothesis of a frustration effect. Moreover, higher coefficients associated with long-term instability suggest that instability creates more anomie in the long run than in the short run.

<Table 3 here> <Table 4 here>

We finally tested whether the effect of instability on crime depends on the macro institutional environment. Firstly, tables 5 and 6 showcase results of estimates where a dummy variable indicating whether a given country belongs to the OECD, for homicide and robbery respectively. As we have already pointed it out, this dummy variable can be introduced only as a multiplicative factor of instability since we used fixed-effects estimator. Both tables show higher coefficients associated with instability variables on their own, suggesting a higher effect of instability on crime in non-OECD countries. Since we already controlled for the effect of the level of income (and its growth rate) on crime in each regression, the OECD dummy variable can be assumed to mainly measure differences of institutional environment between the two groups of countries. However, this variable has several limitations; firstly, it is a very indirect measure of institutional quality. Secondly, since it cannot be introduced additively, we are unable to estimate its direct effect.

<Table 5 here> <Table 6 here>

In order to bypass these issues, we turned to another, more direct and more accurate measurement of institutional quality, by using the composite ICRG index. However, since the ICRG database only began in 1984, the introduction of this variable involves the suppression of the first period covered and a drop in the number of observations. Results are presented in tables 7 and 8 for homicide and robbery respectively. The coefficients associated with the variable of interaction between instability and the ICRG composite index tend to have the expected negative sign even if they are not always significant: the weaker the institutions are, the stronger the effect of instability on crime. Furthermore, the direct effect of instability variables is normally less significant than in the preceding estimates. It suggests that once the direct effect of institutional quality on crime is taken into account, the effect of instability is weaker, supporting the hypothesis that the impact of instability on crime depends on the institutional environment. Finally, in most of the regressions, the ICRG composite index has no direct significant effect on crime.

We also remarked that the elasticities of homicide to the instability of income and to growth volatility are similar, while the level of the elasticities of robbery to instability of income is about twice the level of its elasticities to growth volatility. Since instability of income is measured with regards to a mixed trend which already captures permanent shocks through the lagged variable, while growth volatility reflects both permanent and transitory shocks, we can consider that homicide does not react differently to transitory and permanent shocks, while robbery reacts more to transitory than to permanent ones. This is consistent with our hypothesis that instability influences robbery through the need to smooth income, which is relatively more sensitive to transitory shocks than the instability-induced frustration which is assumed to influence homicide.

<Table 7 here> <Table 8 here>

Conclusion

This paper has considered the impact of macro-economic instability and volatility on crime in an international perspective. Using a panel of developed and developing countries for a maximum of six three-year periods from 1980 to 1997, estimates of the determinants of crime suggest a positive effect of previous macro-economic instability (or growth volatility) on homicide, assumed to be the result of frustration generated by instability, through inaccurate expectations. Instability also leads to increases in robbery, which can be seen as an illegal way of smoothing income. However, this impact of instability is significant only in non-OECD countries, suggesting that the effect of instability on property crime depends on the institutional environment. Of course, the instability variables considered in this paper, as well as other economic variables examined in literature, can only explain a fraction of crime committed.

These results evidence a negative effect of macro-economic instability, which, as far as we know, has yet to be studied. They supplement arguments in favor of policies which aim to reduce macro vulnerability to shocks in developing countries.

Table 1 :

 1 Determinants of homicide rate: simple model (fixed effects) of the impact of instability

	(1)	(2)	(3)	(4)	(5)	(6)	(7)
				HP		HP

Table 2 :

 2 Determinants of robbery rate: simple model (fixed effects) of the impact of instability

	(1)	(2)	(3)	(4)	(5)	(6)	(7)
				HP		HP

Table 3 :

 3 Elasticity of homicide rate to instability depends on the length of instability Dependent variable in logs. AVA: agricultural value added. EE: econometric estimation. HP: Hodrick-Prescott. * significant at 10%; ** significant at 5%; *** significant at 1%.

	Number	AVA instability	Exports instability	GDP per capita instability	Growth volatility
	of years	EE	HP	EE	HP	EE	HP
	10	0.126**	0.135**	0.106**	0.105**	0.079**	0.105***	0.090***
	8	0.106**	0.101*	0.110*** 0.107***	0.078**	0.106***	0.073***
	6	0.082***	0.081**	0.118*** 0.105***	0.066**	0.084***	0.048***
	5	0.085*** 0.096***	0.098*** 0.094***	0.057**	0.065**	0.039***
	4	0.089*** 0.094***	0.090*** 0.084***	0.059**	0.071***	0.033**

Table 4 :

 4 Elasticity of robbery rate to instability depends on the length of instability

	Number AVA instability	Exports instability	GDP per capita instability	Growth volatility
	of years	EE	HP	EE	HP	EE	HP
	10	-0.016	0.034	0.022	0.023	0.122	0.127	0.021
	8	-0.008		0.018	0.006	0.197*	0.192	0.091*
	6	-0.049 -0.044	0.001	-0.004	0.206**	0.203**	0.099**
	5	-0.045 -0.041	-0.013	-0.003	0.228**	0.219**	0.086**
	4	-0.026 -0.021	0.030	0.032	0.194**	0.217**	0.078***

Dependent variable in logs. AVA: agricultural value added. EE: econometric estimation. HP: Hodrick-Prescott. * significant at 10%; ** significant at 5%; *** significant at 1%.

Table 5 :

 5 Impact of instability on homicide rate in OECD and non OECD countries

	(1)	(2)	(3)	(4)	(5)
		HP		HP

Dependent variable in logs. AVA: agricultural value added. HP: Hodrick-Prescott. The length of instability and volatility is 8 years. Robust t-statistics in parentheses. * significant at 10%; ** significant at 5%; *** significant at 1%.

Table 6 :

 6 Impact of instability on robbery rate in OECD and non OECD countriesDependent variable in logs. AVA: agricultural value added. HP: Hodrick-Prescott. The length of instability and volatility is 8 years. Robust t-statistics in parentheses. * significant at 10%; ** significant at 5%; *** significant at 1%.

	(1)	(2)	(3)	(4)	(5)
		HP		HP

Table 7 :

 7 Elasticity of homicide rate to instability depending on the quality of institutions (ICRG composite index)Dependent variable in logs. AVA: agricultural value added. HP: Hodrick-Prescott. The length of instability and volatility is 8 years. Robust t-statistics in parentheses. * significant at 10%; ** significant at 5%; *** significant at 1%.

	(1)	(2)	(3)	(4)	(5)
		HP		HP

Table 8 :

 8 Elasticity of robbery rate to instability depending on the quality of institutions (ICRG composite index)Dependent variable in logs. AVA: agricultural value added. HP: Hodrick-Prescott. The length of instability and volatility is 8 years. Robust t-statistics in parentheses. * significant at 10%; ** significant at 5%; *** significant at 1%.

	(1)	(2)	(3)	(4)	(5)
		HP		HP

See Fajnzylber et al. (2000) and[START_REF] Fougère | L'analyse économétrique de la délinquance. Une synthèse de récents[END_REF] for a review.

The databases are freely available on the website of the Journal of Peace Research: http://www.prio.no/jpr.


David Cachera

Thomas Jensen

David Pichardie

Vlad Rusu

Extracting a data flow analyser in constructive logic

Keywords: Program analysis, constructive logic, lattices, theorem proving, constraint solving

A constraint-based data flow analysis is formalised in the specification language of the Coq proof assistant. This involves defining a dependent type of lattices together with a library of lattice functors for modular construction of complex abstract domains. Constraints are represented in a way that allows for both efficient constraint resolution and correctness proof of the analysis with respect to an operational semantics. The proof of existence of a solution to the constraints is constructive which means that the extraction mechanism of Coq provides a provably correct data flow analyser in Ocaml from the proof. The library of lattices and the representation of constraints are defined in an analysis-independent fashion that provides a basis for a generic framework for proving and extracting static analysers in Coq.

Introduction

Static program analysis is a fully automatic technique for proving properties about the run-time behaviour of a program without actually executing it. The correctness of static analyses can be proved formally by following the theory of abstract interpretation [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximations of fixpoints[END_REF] that provides a theory for relating two semantic interpretations of the same language. These strong semantic foundations constitute one of the arguments advanced in favor of static program analysis. The implementation of static analyses is usually based on well-understood constraint-solving techniques and iterative fixpoint algorithms. In spite of the nice mathematical theory of program analysis and the solid algorithmic techniques available one problematic issue persists, viz., the gap between the analysis that is proved correct on paper and the analyser that actually runs on the machine. While this gap might be small for toy languages, it becomes important when it comes to real-life languages for which the implementation and maintenance of program analysis tools become a software engineering task. To eliminate this gap, we here propose a technique based on theorem proving in constructive logic and the program-as-proofs paradigm. This allows to specify static analyses in a way that ensures their well-formedness and facilitates their correctness proof. Moreover, the constructive nature of the logic means that it is possible to extract, from the proof of existence of a correct program analysis result, a static analyser that maps any given program to their static analysis.

The development of the static analyser is done within the Coq proof assistant. Proofs in Coq are constructive and correspond, via the Curry-Howard isomorphism, to programs in a functional language with a rich type system. The program extraction mechanism in Coq provides a tool for automatic translation of these proofs into a functional language with a simpler type system, namely Ocaml. The extraction mechanism removes those parts of the proof that are only concerned with proving that the result satisfies its specification without actually contributing to its construction. In the case of our static analyser, the constructive part is concerned with calculating a solution to a system of constraints generated from the program. The other part of the proof establishes that a solution to the constraints is indeed a correct approximation of the program's behaviour but does not contribute to the actual construction of the solution.

The methodology that we present here is generic but we have chosen to develop it in the concrete setting of a flow analysis for Java Card byte code, presented in Section 2. The motivation for choosing this particular analysis is that it deals with a minimalistic, yet representative language with imperative, object-oriented and higher-order features, guaranteeing that the approach is transferable to a variety of other analyses. The methodology comprises two phases:

• the modular definition of a library of abstract domains of properties used in the analysis (Section 3). The abstract domains are lattices satisfying a finiteascending-chains condition which makes it possible to extract a provably correct, generic constraint solver based on fixpoint iteration ; • a representation of a constraint-based analysis that allows to extract an analyser from the proof of the existence of a best solution to the constraints, using the program extraction mechanism available in Coq (Section 4) and at the same time allows to prove correctness of the analysis (Section 5).

Section 6 compares with other work on formalizing the correctness of data flow analyses, and Section 7 concludes. Appendices A-E contain the formalisation of the analyser and is included as a service to those readers that want to see the details. However, the paper is written so as to be understandable without having to read these appendices. The Coq sources of the development are available online [START_REF] Pichardie | Coq sources of the development[END_REF].

Notation: Functions whose type depends on the program being analysed will have dependent type F : (P : Program) → T (P ) with type T depending on P . We will write F P for the application of F to a particular program P . The paper uses a mixture of logic and Coq notation. Java Card byte code and Coq functions are written using the teletype font (e.g., push in Section 2 and join in Section 3). Lattices and abstract operations on these as well as their corresponding Coq types are written using the Roman font (e.g., push in Section 2 and the domain of abstract states State illustrated in Figure 2).

A preliminary version of this article was presented at the European Symposium on Programming (ESOP) 2004 [START_REF] Cachera | Extracting a data flow analyser in constructive logic[END_REF]. The present article is a thoroughly revised version that contains a more detailed description of the lattice library, the lattice constructors and the proof of well-foundedness of the lattices, a simplified representation of the constraints generated by the analysis and a more detailed presentation of the correctness proofs.

A Static Analysis for Carmel

The analysis which serves as a basis for our work is a data flow analysis for the Carmel intermediate representation of Java Card byte code [START_REF] Marlet | Syntax of the JCVM language to be studied in the SecSafe project[END_REF] specified using the Flow Logic formalism [START_REF] René | Flow Logic for Carmel[END_REF] and proved correct on paper with respect to an operational semantics [START_REF] Siveroni | Operational semantics of the Java Card Virtual Machine[END_REF]. The language is a byte code for a stack-oriented machine, much like the Java Card byte code. Instructions include stack operations, numeric operations, conditionals, object creation and modification, and method invocation and return. It is given a small-step operational semantics with a state of the form h, m, pc, l, s :: sf , where h is the heap of objects, and m, pc, l, s :: sf is a call stack consisting of frames of the form m, pc, l, s where each frame contains a method name m and a program point pc within m, a set of local variables l, and a local operand stack s (see [START_REF] Siveroni | Operational semantics of the Java Card Virtual Machine[END_REF] for details).

Here and everywhere in the paper, "::" denotes the "cons" operation on lists.

The transition relation → I describes how an instruction I affects the state. We give as example the rules defining the instructions push for pushing a value onto the operand stack, invokevirtual for calling a virtual method, and return for returning from a virtual method call. The expression instructionAt P (m, pc) denotes the instruction found at address (m, pc) in the program P .

The rule (1) reads as follows: the instruction push c at address (m, pc) of state σ = h, m, pc, l, s :: sf has the effect of pushing c on the operand stack s of σ and advancing to the instruction at pc + 1.

instructionAt P (m, pc) = push c h, m, pc, l, s :: sf → push c h, m, pc + 1, l, c :: s :: sf

(1)

instructionAt P (m, pc) = invokevirtual M h(loc) = o m = lookUp(M, class(o)) f = m , 1, V, ε f = m, pc, l, s
h, m, pc, l, loc :: V :: s :: sf → invokevirtual M h, f :: f :: sf

instructionAt P (m, pc) = return f = m , pc , l , s h, m, pc, l, v :: s :: f :: sf → return h, m , pc + 1, l , v :: s :: sf

The rule ( 2) is slightly more complicated. It reads: for M a method name, the instruction invokevirtual M at address (m, pc) of state σ = h, f :: sf requires that the first frame f on the call stack of σ has an operand stack of the form loc :: V :: s, i.e., it starts with a heap location denoted by loc, followed by a vector of argument values V . The actual method that will be called is determined by the lookUp function that searches upwards in the class hierarchy for the methond name M, starting from the class of the object o that resides in the heap h at the location loc. The new method, together with its starting point pc = 1, its vector V of actual parameters, and an empty operand stack ε, constitute a new frame f pushed on top of the call stack of the resulting state σ = h, f :: f :: sf . Note, however, that the second frame f in the call stack is also modified: the sequence loc :: V has been removed from the operand stack of f . This semantics of the invokevirtual instruction (which corresponds to the operational definition of the semantics of Java Card), together with the corresponding rules describing its static analysis, made for the most challenging part of the correctness proofs (we return to this point in Section 5).

Finally, the return rule (3) removes the last frame from the call stack, and transfers the return value v (from the top of the last frame's operand stack) to the operand stack of the calling frame f .

Carmel Flow Logic

The Carmel Flow Logic defined by Hansen [START_REF] René | Flow Logic for Carmel[END_REF] specifies a constraint-based data flow analysis for Carmel. This analysis computes a safe approximation of the states that can occur at any program point during execution of a program. This information can then be used to optimize virtual method calls or verify specific properties on the control flow graph (see e.g. [START_REF] Besson | Model ckecking security properties of control flow graphs[END_REF]). Programs may contain virtual method calls, which are dynamically resolved at execution time ; the analysis reflects this behaviour, and attempts to compute a precise approximation of the called methods and their return values. • a reference to object o is approximated by an abstract value V (written ref (o) ∼ V ) whenever V is a set of classes that contains the class of o, • the vector of local variables l and operand stack s at a given program address (m, pc), are approximated pointwise, • a concrete state h, m, pc, l, s :: sf is approximated by an abstract state Σ = ( Ĥ, ( L, Ŝ)) whenever h ∼ Ĥ, l ∼ L(m, pc), and s ∼ Ŝ(m, pc).

The abstract domains are further described in Section 3. An important property of the approximation relation ∼ is the monotonicity with respect to the abstract order . It says that, for each concrete value a (be it a heap, a stack, or a vector of local variables) and abstract values A, A in the corresponding abstract domain, if a ∼ A and A A then a ∼ A holds as well. This property of ∼ is proved in Coq once and for all for each concrete and corresponding abstract domain. The relation ∼ is used extensively in Section 5 where we show how to prove correctness of the analysis in Coq.

The specification of the flow logic consists of a set of inference rules that for each Carmel instruction define a constraint over an abstract state Σ ∈ State. For Σ = Ĥ, L, Ŝ to be a correct abstraction of program P , Σ must satisfy the constraints of the instructions of P . For example, if a push instruction is present at address (m, pc), the following constraints should be satisfied:

push c, Ŝ (m, pc) Ŝ (m, pc + 1) (4) L (m, pc) L (m, pc + 1) ( 5
)
where push is the abstract push operation from the abstract domain of stacks.

The constraints ( 6) and ( 7) below are attached to the invokevirtual instruction. Other constraints attached to this instruction can be found in the Appendix. Together, the constraints ( 6) and ( 7) describe the relation between the value of the abstract stack Ŝ at an address (m, pc) where a method named M is called by an invokevirtual instruction, and the value of Ŝ at the address (m, pc + 1) that follows the method's return.

pop n Ŝ(m, pc), 1 + nbArgs(M) pop Ŝ(m, pc + 1) (6)
∀cl ∈ top Ŝ(m, pc) , ∀m ∈ lookUp(M, cl).

(a) [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF] top Ŝ(m , Ret(m )) top Ŝ(m, pc + 1) (b)

In particular, the constraint [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF], explained below, plays a particular role in the correctness proof described in Section 5. Assume that the program performs an invokevirtual M instruction at an address (m, pc). The constraint [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF] computes both (a) a set of methods that contains the method actually called by invokevirtual, and (b) an over-approximation of the return values of all the methods computed at Step (a).

• Step (a) simulates the semantics of invokevirtual (rule ( 2)). The rule says that the method actually called is found by looking up for methods named M, in the class of the object referenced by the top of the concrete operand stack when the execution is at address (m, pc). The constraint [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF] simulates this behaviour at the abstract level: it searches the class hierarchy for methods called M starting from all the classes contained in the corresponding abstract value top Ŝ(m, pc) . • Step (b) is performed by simulating the semantics of the return instruction.

By the semantics rule (3), the return value of the method m actually called is placed on the top of the operand stack at address (m, pc + 1). Hence, the constraint [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF] imposes that top Ŝ(m, pc + 1) is greater than the abstract return values top Ŝ(m , Ret(m )) of all methods m computed at Step (a), where Ret(m ) is a virtual program point used for collecting abstract results of each method m . Note that Step (a) implicitly assumes that the abstract value top Ŝ(m, pc) correctly approximates the top of the concrete operand stack when execution is at address (m, pc), i.e., before the invokevirtual instruction. That is, the abstract value top Ŝ(m, pc) is a set of classes which contains the class of the object o that is referenced by the top of the concrete operand stack when execution is at address (m, pc). This assumption becomes a proof obligation, to be discharged when proving the correctness of the analysis (cf. Section 5).

Constructing abstract domains

In this section we define a data type for lattices (lattice A), parameterised by the type of elements of the lattice. We also define higher-order functions which build a lattice object from other lattice objects. This allows to construct the abstract domains (of local variables, stacks, etc.) in a compositional fashion from a collection of base abstract domains. The advantage of this modular technique of combining and building lattices is that we do not have to prove properties (such as the finite ascending chain condition, see below) for one big, final lattice, but can do so in a modular fashion for every type of lattice used. Furthermore, local changes to the lattice structure do not invalidate the overall proof.

A lattice object is a record structure with two families of fields: the functional fields which are the operations that will remain in the extracted Ocaml code, and the logical fields that contain properties about the lattice. E.g., the field join is a functional field that contains the least upper bound operator of the lattice, whereas the field acc property is a logical field stating that the lattice satisfies the ascending chain condition. The lattice type is conveniently defined as a record type in Coq, as shown in the following Coq declaration, where only details for the order relation, the join operation and the well-foundedness of the lattice are given. The well-foundedness field will be explained in detail in Section 3.1.

Record Lattice [A: Set]: Type := { eq : A → A → Prop; eq prop : ... ;; eq is an equivalence relation order : A → A → Prop; order refl : ∀x, y : A (eq x y) ⇒ (order x y); order antisym : ∀x, y : A (order x y) ⇒ (order y x) ⇒ (eq x y); order trans : ∀x, y, z : A (order x y) ⇒ (order y z) ⇒ (order x z); join : A → A → A; join bound1 : ∀x, y : A (order x (join x y)); join bound2 : ∀x, y : A (order y (join x y)); join least : ∀x, y, z : A (order x z) ⇒ (order y z) ⇒ (order (join x y) z); eq dec : A → A → bool eq dec prop : ... ;; eq dec is a correct test of equality bottom : A; bottom_prop : ... ;; bottom is the least element top : A; top_prop : ... ;; top is the greatest element acc property : (well founded A (λx, y : A, ¬(eq y x)∧(order y x))) }

In this large object, the properties in the logical fields are only necessary during the Coq development to ensure the logical coherence of the structure. Hence only the four functional fields appear in the extracted Ocaml lattice type:

type 'a lattice = { join : ('a → 'a → 'a); eq_dec : ('a → 'a → bool); bottom : 'a; top : 'a }
Declaring a structure of Lattice type will result in a series of proof obligations, one for each of the logical fields. Of these, the last property acc property is the most difficult to establish. It expresses that the strict dual order is wellfounded, or, in other words, that there are no infinite, ascending chains. It is the key property used to prove the termination of the final analyser. Thus, strictly speaking we are dealing with lattices satisfying the finite ascending chain-condition but we will for convenience use the general term lattice in the rest of this document.

Lattice constructors and proof of well-foundedness

The lattices are built from two base lattices using four lattice constructors. These constructors are not tied to this particular analysis and can be reused in other contexts. The most difficult part of each lattice construction is the proof of preservation of acc property (the ascending chain condition), which is essential for defining an analyser that terminates. This is essentially a termination proof which is typically hard to conduct in a proof assistant because the standard techniques of structural orders or well-chosen measures do not apply in the case of lattice orders. The proof has to operate directly with the definition of a well-founded order. We use the standard inductive definition of a well-founded relation, as used in the built-in Coq predicate well founded:

Definition 1 Let A be a type and ≺ a binary relation on A.

• The accessibility predicat is inductively defined by: an element x of type A is accessible if and only if all the predecessors of x are accessible, • a binary predicate ≺ on a type A is well-founded if all the elements of A are accessible for ≺.

The prodLattice function is the standard cartesian product with the pointwise order (x 1 , y 1 ) A×B (x 2 , y 2 ) iff

x 1 A x 2 ∧ y 1 B y 2
The ascending chain condition of this structure is proved using the fact that the strict reverse order is a sub-relation of the lexicographic product

(x 1 , y 1 ) A×B (x 2 , y 2 ) =⇒ x 1 A x 2 ∨ (x 1 = A x 2 ∧ y 1 B y 2 )
The sumLattice function builds the separate sum of two lattices A and B according to the Hasse diagram of Figure 1(a). The acc property proof of this lattice is done following the different layers of the diagram: first, we prove that the top element is accessible (no predecessor); then, that all the elements of A, B are accessible (using the fact that is accessible and A well-founded). Finally, we prove that ⊥ is accessible because all its predecessors are accessible (they are elements of A ∪ B ∪ { }).

The stackLattice constructor builds the lattice of stacks of elements of type A. In this lattice, stacks with different sizes are incomparable, according to The ascending chain condition proof again follows the layers of the Hasse diagram but is more technical because of the infinite width of the lattice: for the middle layer, that is, the level of stacks, we use an induction on the stack size. The case of the empty stack is trivial (no predecessor) and for the induction step, we observe that strict inverse order for stacks of size n + 1 is a sub-relation of the lexicographic product between (A, ) (which is supposed well-founded) and the set of stacks of size n (which is well-founded for the strict inverse order by induction hypothesis).

A B ⊥ (a) <> stacks of size 1 • • • stacks of size n • • • ⊥ (b) ⊥ (c)
(x 1 :: l 1 ) n+1 (x 2 :: l 2 ) =⇒ x 1 A x 2 ∨ (x 1 = A x 2 ∧ l 1 n l 2 )
The fourth constructor arrayLattice builds the type of arrays whose elements live in a lattice and whose size is bounded by a parameter max, using a pointwise order. Notice that arrays of different sizes may be comparable whereas this is not the case for the order we have defined on stacks.

t 1 t 2 iff ∀i ∈ {1, . . . , max}, t 1 [i] A t 2 [i]
The array lattice frequently occurs in flow-sensitive analyses where the number of abstract variables depends on the program to analyse-these are then conveniently collected in an array. An efficient implementation of arrays is therefore crucial for obtaining an efficient extracted code, and we have optimized it by using an efficient tree representation of integer maps in the spirit of [START_REF] Okasaki | Fast mergeable integer maps[END_REF]. The crucial ideas of this implementation are

• to represent arrays using binary trees whose nodes are elements of the array • to represent indexes using a binary notation; an element at position i in an array is found by interpreting the binary notation of i as the "path" to follow from the root • to have a lazy structure: if a searched node is missing, its value is by convention ⊥ A , which allows to represent an array whose elements are all ⊥ A by an empty leaf. The acc property proof of this lattice is performed by defining an order on trees (a leaf is smaller that any tree; two nodes are smaller if their heads are in the A relation and if their descendents are smaller as well), proving its well-foundedness, and, finally, connecting this order to the array order. It is certainly the most technical of this library. More details on this proof can be found in the corresponding Coq development.

State

In addition to these four functors, two base lattices are defined:

• the flat lattice of integer constants (as used e.g., in constant propagation analysis), • the lattice of finite sets over a subset {0, . . . , max} of integers: again, an efficient implementation is proposed, by encoding sets using boolean arrays, hence based on the arrayLattice functor and two-valued lattice of Figure 1(c).

The lattice employed in our particular analysis is given a graphical representation in Figure 2 (see Appendix for a mathematical description of the lattice).

In this diagram, each node represents a lattice functor whose parameters are the sons of the node. For the array functor and the finite-set lattice we write the index domain inside brackets. The modular construction saves a considerable amount of time and effort, e.g., compared to proving acc property for the lattice in Figure 2 as a whole.

Iterative constraint solving over lattices

Implementing a static program analyser involves building a constraint solver that can compute a solution to constraints like the flow logic constraints shown in Section 2 [START_REF] Nielson | Principles of Program Analysis[END_REF]. The problem of solving a set of constraints over a lattice L of abstract values can be transformed into calculating a fixpoint of a monotone function over L-a fixpoint that for reasons of precision should be as small as possible. More precisely, let f : L → L be a monotone function over L. The basic fixpoint operator lfp takes such a monotone function f and computes the least element x of L verifying f (x) = x. Furthermore, by a corollary of the Tarski's Fixed Point Theorem, this element can be iteratively calculated as the limit of the (stabilizing) sequence (f n (⊥)) n∈N . Formally, we define the operator lfp of type

(A:Set) → (L:(Lattice A)) → (f:(A→A)) → (monotone L f) → ∃x:A, (eq L x (f x)) ∧ (∀y:A (eq L y (f y)) ⇒ (order L x y))
That is, lfp takes four arguments : a data type A, a lattice L on A, a function f on A and a proof that f is monotone. It returns the least fixed point of f . We prove in Coq that this type is non-empty, which here consists in instantiating the existentially quantified x in the type definition by lim n→∞ f n (⊥).

The extraction mechanism of programs from proofs generates for lfp the following Ocaml code, in which the purely logical part of the proof (i.e., the part concerned with proving that the chosen witness verifies the fixpoint equation) has been removed:

let lfp L f = let rec aux x = if (L.eq_dec x (f x)) then x else aux (f x) in aux L.bottom
We use x = f (x) as halting condition here, but, as is well known from the fixed point theory, we could equally well have used the post-fixed point condition f (x)

x. The equality test appears to be more efficient for the majority of lattices used in our case study.

In order to use the lfp operator to solve the constraints arising from the Java Card flow analysis it must be extended to a function lfp list that can deal with systems of the form {f i (x) x} i=1,...,n

Given a list f 1 , . . . , f n of monotone functions of type L → L, the operator lfp list computes the least solution x of the system by a round-robin iteration strategy in which the constraints are iterated in increasing order. This computation is implemented by applying the lfp operator on the monotone function fn • • • • • f1 , where fi (x) = x f i (x) for every index i. The fact that this computes a solution to the constraint system is formalised in the type of lfp list, which is expressed in Coq as follows:

(l: (L → L) list) → (∀f ∈ l, (monotone L f)) → ∃x:A, (∀f ∈ l, (order L (f x) x)) ∧ (∀ y:A (∀f ∈ l, (order L (f y) y)) ⇒ (order L x y))

This type means that any application of lfp list to a list of functions f i must be accompanied by a proof of the monotonicity of each f i . Read at a proof-theoretic level, it states that from the proofs of monotonicity of the f i we can prove the existence of a least common post-fixpoint for all of the f i . This function will be used as a generic constraint solver in Section 4.

Constructive Constraints

We now turn to the problem of building an analyser that implements the flow analysis from Section 2. The development will be structured into three phases:

(1) The generation of a set of constraints for each instruction.

(2) The building of an analyser analyse that computes an abstract state verifying all the constraints generated for a given program. (3) The proof of correctness of these constraints wrt. the Carmel semantics.

In the rest of this section, we focus on the constraint generation and resolution (Phases 1 and 2). In Section 5 we describe the proof of correctness (Phase 3).

Let P

Σ be the predicate meaning that the abstract state Σ verifies all constraints of program P (this predicate is defined formally in Definition 5 below). Phases 2 and 3 correspond to proving the following two theorems: Theorem 2 For each program P , there exists an abstract state Σ satisfying all constraints of P :

∀P : Program, ∃ Σ : State P . P Σ
The constructive proof of this theorem provides the analyser itself: the abstract state Σ we construct corresponds to analyse(P ).

Generating the constraints

When formalising the analysis, several representations of the constraints are possible.

• For the correctness proof (Phase 3), it is sufficient to know which order relation is induced by the constraints on a given set of components of the abstract state. Using an inductive definition for constraints would naturally provide the necessary predicates for this phase. Relational constraints written as ( 4)-( 7) could be translated in Coq in a straightforward manner using inductive definitions. • On the other hand, the construction of an effective analyser (Phase 2) requires to represent constraints in a functional form like f (X) X. This representation is typically difficult to extract directly from inductive definitions. 2This is why an internal representation of constraints is defined in Phase 1, which allows for both interpretations and leaves room for reuse in other analyses.

Looking at Formulas (4) and ( 5) for the push instruction (Section 2.1), we note that the representation of constraints must contain the following informations: (i) the components of the abstract state that are involved in the constraint, (ii) a start address ad 1 and an end address ad 2 of the data flow, and (iii) the transformation F that is applied to the data that flows. For example, constraint (4) only affects the abstract state Ŝ, and we have ad ... [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximations of fixpoints[END_REF] where each constructor represents a type of dependency between components of the abstract state. For example, S2S is a constructor to express a constraint on an abstract stack which depends on another abstract stack. For the particular analysis discussed here eleven constructors were employed.

Each constraint, initially acting on a part of the abstract state, is extended to a function on the whole abstract state, using a mapping

F [[•]] : Constraint P → State P → State P
for which we prove that it preserves the monotonicity of constraints. E.g., for the push instruction

F [[(S2S ad 1 ad 2 F )]] := λ(H, L, S). (H, L, S[ad 2 → F (S(ad 1 ))]) F [[(L2L ad 1 ad 2 F )]] := λ(H, L, S). (H, L[ad 2 → F (L(ad 1 ))], S)
Based on this definition of the constraints we define a function cst gen, which for each address, returns the list of constraints for the corresponding instruction in a syntax of the form [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximations of fixpoints[END_REF]. Continuing with the push instruction, the corresponding code part is:

cst gen P := λ(m,pc)
Case instructionAt P (m,pc) of | (push c) → (S2S (m,pc) (m,pc+1) λ Ŝ. push ĉ, Ŝ ) ::

(L2L (m,pc) (m,pc+1) λ L. L) ... The well-formedness of this function depends on the actual program P being analysed because every instance of (m, pc) must be shown to refer to a valid program point of P . In a paper-and-pencil proof, this is often left as an implicit hypothesis. In a formal proof however, this fact must be stated explicitly. In a dependently-typed framework, the constraint generation will thus be parameterised by the program being analysed, yielding a function cst gen P which takes as argument an address (m, pc) in the program P and generates the constraints corresponding to the type of instruction at (m, pc).

We now can formally define what it means for an abstract state Σ to verify all the constraints of a program P .

Definition 5 Let Addr P denote the set of addresses appearing in P :

P Σ ≡ ∀(m, pc) : Addr P , ∀c ∈ cst gen P (m, pc). F [[c]]( Σ) Σ

Construction of the analyser

Recall that the goal is to build an analyser that, given an input program, computes an abstract state that verifies all the constraints of the program. We construct a function analyse of dependent type (P : Program) → State P which must verify ∀P : Program, P analyse(P ) (10) In addition, we want to obtain a non-trivial solution of the constraint system: e.g., an analyser returning the top element of the lattice for any input is a correct solution, but of poor interest. We thus add the requirement that our solution is the least solution of the constraint system:

∀P : Program, Σ : State P P Σ ⇒ analyse(P ) Σ (11)
The constraint resolution tool is based on the generic solver lfp list (8) described in Section 3.2. The most difficult part of the work has already be done during the definition of the solver, i.e., proof of termination and correctness.

It is instantiated here with the particular abstract state lattice of the analysis (depicted in Figure 2); then,

• For each instruction of program P , the constraints are collected from the lists defined by cst gen P (cf. Section 4.1). • Each constraint is translated into a function on abstract states using the mapping F . The resulting list of functional constraints is called collect func P .

As F preserves the monotonicity of constraints, we conclude that ∀f ∈ collect func P f is monotone [START_REF] René | Flow Logic for Carmel[END_REF] We now have all the ingredients to define the constraint solver:

analyse(P ) = lfp list( State P , collect func P , collect func monotone)
where collect func monotone is the name given to the proof of [START_REF] René | Flow Logic for Carmel[END_REF].

By the properties of lfp list (defined by Formula ( 8)) we know that analyse(P ) is the least abstract state Σ in State P verifying ∀f ∈ collect func P f ( Σ) Σ (13)

Thus, analyse(P ) is the least Σ satisfying P Σ.

We stress that this approach defines a methodology that remains valid for other analyses. Indeed, all proofs in this section are independent of the system of constraints defined by the user. They only depend on the different types of constraints introduced as in (9) (S2S, L2L,...). As a consequence, modifications to the system of constraints only affect proofs made about the monotonicity of constraints and during Section 5, rather than the construction and the correctness of the solver itself.

Correctness

Section 4 has shown that an effective solver for the constraints of a program exists. We now show that the solver is indeed a correct analyser for the program. The analysis is correct if every abstract state Σ satisfying all the constraints of the analysis is an approximation of the reachable states [ [P ]] of the program:

∀P : Program, Σ : State P . P Σ ⇒ [[P ]] ∼ Σ (14)
The implication [START_REF] Lerner | Automatically proving the correctness of compiler optimizations[END_REF] has been proved in Coq by well-founded induction on the length of the program executions. The base step is trivial. The induction step depends on whether the last instruction is return or some other instruction.

Induction Step: the non-return Instructions

For I an instruction, let → I denote the transition relation of I (examples of which have been given in Section 2). The general form of the induction step for any Carmel instruction I = return is of the following form.

P Σ =⇒ ∀σ, σ ∈ [[P ]], σ ∼ Σ ∧ σ → I σ ⇒ σ ∼ Σ (15)
That is, if a state σ is approximated by an abstract state Σ that satisfies the constraints of program P , and if, by performing instruction I, the state σ becomes σ , then σ is approximated by Σ as well. We now sketch the proof of ( 15).

(1) A Coq script unfolds the definition of the transition rule for instruction I.

(2) Then, another script unfolds the definitions of σ ∼ Σ and P Σ and automatically turns them into hypotheses of the current Coq goal3 . For example, if σ = h, m, pc, l, s :: sf , Σ = ( H, L, S), and I = push c then the following hypotheses are generated:

s ∼ S(m, pc), push c, S (m, pc) S (m, pc + 1) (16)
(3) Next, the conclusion of the Coq goal: σ ∼ Σi.e., the new state σ is approximated by the abstract state Σ = ( H, L, S) -is split into three subgoals, one for each of the components ( H, L, S) of Σ.

For I = push c, the subgoal corresponding to the abstract stack S is

c :: s ∼ S(m, pc + 1) (17)
(4) Finally, the subgoals generated at Step 3 are proved using the hypotheses generated at Step 2 and monotonicity of ∼ with respect to (cf. Section 2). For I = push c, the only non-trivial subgoal is represented by Formula [START_REF] Nielson | Principles of Program Analysis[END_REF]. It is proved using the fact that push is a correct abstraction of the concrete push operator "::", i.e., c :: s ∼ push c, S (m, pc) . This, together with the hypothesis ( 16) and the monotonicity of the ∼ relation for stacks, implies the subgoal [START_REF] Nielson | Principles of Program Analysis[END_REF], and the proof is done.

Induction

Step: the Case of the return Instruction Formula (15) above has the general aspect of the induction step in a proof by simple induction. That is, if the abstract state Σ approximates the concrete state σ, then Σ also correctly approximates all immediate successors σ of σ. However, this simple implication could not be proved for the return instruction. This is because the effect of the return is simulated by a constraint (cf. Formula ( 7)) attached to a different instruction: the invokevirtual instruction that called the method now performing the return. As seen in Section 2.1, in order to evaluate which methods may have been called, the constraint ( 7) must be used together with the assumption that the top of the concrete stack at the address (m, pc) where the invokevirtual instruction has been performed, is correctly approximated by the top of the abstract stack top Ŝ(m, pc) .

More generally, we need to assume that the concrete state σ where the invokevirtual instruction has been performed, was correctly approximated by the abstract state Σ as well. But σ may have been encountered arbitrarily far in the past. Hence, our proof of the induction step for the return instruction uses a well-founded induction hypothesis, which imposes that the whole proof of correctness be done by well-founded induction.

Let [[P ]]

<n denote the set of states of program P that are reachable using less than n instructions. The induction step for I = return is:

∀n ∈ N.[∀σ ∈ [[P ]] <n . σ ∼ Σ] ⇒ ∀σ ∈ [[P ]] <n , ∀σ .[ σ → I σ ⇒ σ ∼ Σ] (18)
Formula (18) reads: if the abstract state Σ approximate all earlier states σ (well-founded induction hypothesis); and σ evolves, by performing a return instruction, into σ ; then, Σ approximates σ as well.

The proof of Theorem ( 18) is substantially more involved than the proofs of Theorems [START_REF] Marlet | Syntax of the JCVM language to be studied in the SecSafe project[END_REF]. It should be pointed out that this difficulty had been avoided by a previous pencil-and-paper proof [START_REF] René | Flow Logic for Carmel[END_REF], where some details -the actual JavaCard semantics of the invokevirtual instruction -have been overlooked.

Related work

Proving correctness of program analyses is one of the main applications of the theory of abstract interpretation [START_REF] Cousot | Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximations of fixpoints[END_REF]. However, most of the existing proofs are pencil-and-paper proofs of analyses (formal specifications) and not mechanised proofs of analysers (implementations of analyses). The only attempt of formalising the theory of abstract interpretation with a proof assistant is that of Monniaux [START_REF] Monniaux | Réalisation mécanisée d'interpréteurs abstraits[END_REF] who has built a Coq theory of Galois connections. Prost in his thesis [START_REF] Prost | Interprétation de l'analyse statique en théorie des types[END_REF] conduces a theoretical study of the relation between type theory and program analysis, but this work did not lead to an implementation of a concrete analysis.

Mechanical verification of program processing tools has so far mainly focussed on the correctness of optimising compilers. Genet et al. [START_REF] Genet | A Java Card CAP converter in PVS[END_REF] use the generic proof assistant PVS for proving the correctness of algorithms for transforming Java Card byte code into the more compact CAP format. Similar work was done by Denney [START_REF] Denney | The synthesis of a Java Card tokenisation algorithm[END_REF], using the program extraction mechanism of Coq. These optimisations do not involve any sophisticated static analysis. Lerner et al. [START_REF] Lerner | Automatically proving the correctness of compiler optimizations[END_REF] have developed Cobalt, a dedicated programming language for writing C program optimisers and automatically proving their soundness. This language allow to define statement transformation guarded by predicates on execution traces. To prove the correctness of the optimisation, these transformation patterns produce proof-obligations to be discharged by an automatic theorem prover. The authors propose an execution engine to compile Cobalt descriptions in an executable form. The framework allows to write several optimisations whose correctness is automatically proved by the Simplify theorem prover. The scope of this work seem currently restricted to intra-procedural analysis with simple lattices of approximations. Finally, ongoing work in the French research action "Concert" [START_REF] Leroy | French ARC Concert research project : compilateurs certifiés[END_REF] currently explores the feasibility of developing a realistic certified compiler in Coq. First results concern the certification of three classical low-level optimizations based on dataflow analysis and some first experiments in program transformation.

Previous formalisations of static analyses for Java (Card) byte code have all dealt with intra-procedural type verification. In contrast, we have also shown how to handle inter-procedural data flow analysis in a natural manner; this is due to the fact that we use the general setting of Flow Logic [START_REF] Hanne | Flow Logics for Constraint Based Analysis[END_REF] and constraint-based analysis. Research on mechanical verification of the Java byte code verifier includes that of Barthe et al. [START_REF] Barthe | A Formal Executable Semantics of the JavaCard Platform[END_REF] who have shown how to formalise the Java Card byte code verification in the proof assistant Coq by isolating the byte code verification in an executable semantics of the language. In [START_REF] Barthe | Jakarta: A Toolset for Reasoning about JavaCard[END_REF], they propose to automate the derivation of a certified verifier from a formalisation of the JCVM. Their approach does not rely on a general theory of static analysis, and is oriented towards type verification. Bertot [START_REF] Bertot | Formalizing a JVML Verifier for Initialization in a Theorem Prover[END_REF] used the Coq system to extract a certified bytecode analyser specialized for object initialization, but no attention has been paid to the efficiency of the analyser. In [START_REF] Coglio | Towards a Provably-Correct Implementation of the JVM Bytecode Verifier[END_REF], Coglio et al. described their ongoing efforts to implement a bytecode verifier by refinement from the specification of a constraint-solving problem on lattices. Klein and Nipkow [START_REF] Klein | Verified Bytecode Verifiers[END_REF] have proved the correctness of a Java byte code verifier using the proof assistant Isabelle/HOL. In particular their work includes a correctness proof of Kildall's iterative workset algorithm for solving data flow equations. They also provide a modular construction of lattices. The major difference with our approach is the use of abstract data types that are not implementable as such.

An alternative to the Coq proof extraction mechanism is the B method that has had considerable industrial success. Casset et al. [START_REF] Casset | Formal Development of an verifier for Java Card Byte Code[END_REF] have extracted a proofcarrying code-based on-card bytecode verifier for Java Card from a high-level specification by a succession of refinement steps using the B technique. The development required the proof of thousands of proof obligations, of which several hundreds could not be dealt with automatically by the B prover. The B tool could most probably be used for building an analyzer like ours but we doubt that using B would lead to a simpler proof effort. In addition, the program extraction mechanism in B does not enjoy the same solid foundations as that of Coq. Hence our decision to base our development on Coq.

Conclusion

The results presented in this article demonstrates that it is feasible to construct a non-trivial, provably correct data flow analyzer using the program extraction mechanism of constructive logic implemented in Coq. This bridges the gap that often exists between a paper-specification of an analysis and the analyser that is actually implemented. Our approach applies to analyses expressed in the constraint-based Flow Logic specification framework and is hence applicable to a large variety of program analyses for different language paradigms. We have instantiated it to a data flow analysis for Java Card. To the best of our knowledge, it is the first formal construction (with proof of correctness) of a data flow analysis other than the Java byte code verifier.

Formalising a program analyser in a proof assistant imposes a strict discipline that catches a certain number of bugs, including typing errors in the spec-ification. The present development revealed several (innocuous) inaccuracies in the pencil-and-paper specifications and proof of correctness. Moreover, it pinpointed the adjustment that had been made of the actual semantics of Java Card in the correctness proof on paper-an adjustment that (as argued in Section 5.2) made the proof far simpler than a proof done against a more accurate semantics.

Our methodology makes use of the proof-as-programs paradigm. This paradigm is sometimes presented as developing programs as a by-product of building a constructive proof interactively and incrementally for an "existential" theorem with a proof assistant. While this presentation is conceptually simple and appealing, the development of any non-trivial piece of software (including the present analyser) rather tends to be done by defining (most of) the function and then showing that it is indeed a witness to the theorem. This technique has the further advantage that it is simpler to control the efficiency of the resulting program. In our case, the provably correct analyser was developed by splitting the correctness proof into

• an existential proof of a solution to a constraint system from which a constraint solver can be extracted and, • a proof that the solutions to the constraint system are correct approximations of the semantics of the analysed program; this proof does not contribute to the actual construction of the solution.

The methodology includes several steps of varying complexity. The development of the lattice library required a Coq expert to structure the proofs of the properties associated with the lattice constructors. Once this library in place, it turned out to be a relatively straightforward task to prove correctness of the constraint generation and to extend the constraint generation to instructions others than those originally studied. It took a Coq neophyte less than two months to complete the correctness proof, including the time and effort needed to understand the general framework of the project. Only basic features of the tool, those available in any other general-purpose theorem prover, have been employed in the correctness proof.

The program extraction mechanism has a reputation for producing inefficient programs. This is not the case with our methodology: the extracted analyser is about 2000 lines of Ocaml code and takes only a few seconds to analyse 1000 lines of bytecode. The extracted version of analyse has now a type Program → State because Ocaml does not have dependent types. As mentioned above, the methodology leaves some possibilities for programming the resolution mechanism. This, and the inclusion of widening operators, is one important step forward to be accomplished. Another is further automation of the proof obligations arising during the development of the analyser in order to make the methodology the standard way of implementing static analysers.

A Syntax

Instruction ::= nop push c pop dup dup2 swap numop op                   

  prodLattice : (Lattice A) → (Lattice B) → (Lattice A*B) sumLattice : (Lattice A) → (Lattice B) → (Lattice (lift A+B)) stackLattice : (Lattice A) → (Lattice (stack A)) arrayLattice : (max:nat) → (Lattice A) → (Lattice (array max A))

Fig. 1 .

 1 Fig. 1. Hasse diagrams of lattices the Hasse diagram of Figure 1(b).The ascending chain condition proof again follows the layers of the Hasse diagram but is more technical because of the infinite width of the lattice: for the middle layer, that is, the level of stacks, we use an induction on the stack size. The case of the empty stack is trivial (no predecessor) and for the induction step, we observe that strict inverse order for stacks of size n + 1 is a sub-relation of the lexicographic product between (A, ) (which is supposed well-founded) and the set of stacks of size n (which is well-founded for the strict inverse order by induction hypothesis).

Theorem 3

 3 An abstract state verifying all the constraints of a program P is a correct approximation of the operational semantics of P : ∀P : Program, Σ : State P . P Σ ⇒ [[P ]] ∼ Σ where [[P ]] denotes the set of reachable states of program P and ∼ is the correctness relation between concrete domains of the operational semantics and the abstract domains. Putting these two theorems together, we get the correctness of the analyser: Theorem 4 (Global Correctness) [[P ]] ∼ analyse(P )

1 =

 1 pc, ad 2 = pc + 1, and F = λ Ŝ. push(c, Ŝ). This naturally leads to an inductive data type of the form type Constraint P = | S2S of Address * Address * ( Stack P → Stack P ) | L2L of Address * Address * ( LocalVar P → LocalVar P )

  * LocalVar = Var → Value Frame = ProgCount × nameMethod × LocalVar × Stack CallStack = Frame * Object = nameClass × (FieldName → Value) Heap = Reference → Object ⊥ State = Heap × CallStackinstructionAt P (m, pc) = nop h, m, pc, l, s :: sf → nop h, m, pc + 1, l, s :: sf instructionAt P (m, pc) = push c h, m, pc, l, s :: sf → push c h, m, pc + 1, l, c :: s :: sf instructionAt P (m, pc) = pop h, m, pc, l, v :: s :: sf → pop h, m, pc + 1, l, s :: sf instructionAt P (m, pc) = dup h, m, pc, l, v :: s :: sf → dup h, m, pc + 1, l, v :: v :: s ::sf instructionAt P (m, pc) = dup2 h, m, pc, l, v 1 :: v 2 :: s :: sf → dup2 h, m, pc + 1, l, v 1 :: v 2 :: v 1 :: v 2 :: s :: sf instructionAt P (m, pc) = swap h, m, pc, l, v 1 :: v 2 :: s :: sf → swap h, m, pc + 1, l, v 2 :: v 1 :: s :: sf instructionAt P (m, pc) = numop op h, m, pc, l, n 1 :: n 2 :: s :: sf → numop op h, m, pc + 1, l, [[op]](n 1 , n 2 ) :: s :: sf instructionAt P (m, pc) = load x h, m, pc, l, s :: sf → load x h, m, pc + 1, l, l[x] :: s :: sf instructionAt P (m, pc) = store x h, m, pc, l, v :: s :: sf → store x h, m, pc + 1, l[x → v], s :: sf instructionAt P (m, pc) = if pc n = 0 h, m, pc, l, n :: s :: sf → if pc h, m, pc , l, s :: sf instructionAt P (m, pc) = if pc n = 0 h, m,pc, l, n :: s :: sf → if pc h, m, pc + 1, l, s :: sf instructionAt P (m, pc) = goto pc h, m, pc, l, s :: sf → goto pc h, m, pc , l, s ::sf instructionAt P (m, pc) = new cl ∃c ∈ classes(P ) with nameClass(c) = cl (h , loc) = newObject(cl, h) h, m, pc, l, s :: sf → new cl h , m, pc + 1, l, loc :: s :: sf instructionAt P (m, pc) = putfield f h(loc) = o o = o[f → v] h, m, pc, l, v :: loc :: s :: sf → putfield f h[loc → o ], m, pc + 1, l, s :: sf instructionAt P (m, pc) = getfield f h(loc) = o h, m, pc, l, loc :: s :: sf → getfield f h, m, pc + 1, l, fieldValue(o, f ) :: s :: sf instructionAt P (m, pc) = invokevirtual M h(loc) = o m = lookUp(M, class(o)) f = m , 1, V, ε f = m,pc, l, s h, m, pc, l, loc :: V :: s :: sf → invokevirtual M h, f :: f :: sf instructionAt P (m, pc) = return f = m , pc , l , s h, m, pc, l, v :: s :: f :: sf → return h, m , pc + 1, l , v :: s :: sf h, m, pc, l, s :: sf ∼ State Ĥ, Ŝ, L iff h ∼ Heap Ŝ ∧ l ∼ h LocalVar L (m, pc) ∧ s ∼ h Stack Ŝ (m, pc) E Constraints Ĥ, L, Ŝ |= (m, pc) : nop iff Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : push c iff push c, Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : pop iff pop Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : numop op iff binop op, Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : dup iff push top Ŝ (m, pc) , Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : dup2 iff push top Ŝ (m, pc) , push top pop Ŝ (m, pc) , Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : swap iff push top pop Ŝ (m, pc) , push top Ŝ (m, pc) , pop pop Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : load x iff push apply L (m, pc) , x , Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : store x iff pop Ŝ (m, pc) Ŝ (m, pc + 1) subst L (m, pc) , x, top Ŝ (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : if pc iff test =0 top Ŝ (m, pc) , pop Ŝ (m, pc) Ŝ (m, pc ) test =0 top Ŝ (m, pc) , L (m, pc) L (m, pc ) test =0 top Ŝ (m, pc) , pop Ŝ (m, pc) Ŝ (m, pc + 1) test =0 top Ŝ (m, pc) , L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : new cl iff push {cl} , Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) default(cl) apply Ĥ, cl Ĥ, L, Ŝ |= (m, pc) : getfield f iff ∀cl ∈ top Ŝ (m, pc) : push apply apply Ĥ, cl , f , pop Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) Ĥ, L, Ŝ |= (m, pc) : putfield f iff pop pop Ŝ (m, pc) Ŝ (m, pc + 1) L (m, pc) L (m, pc + 1) ∀cl ∈ top pop Ŝ (m, pc) : top Ŝ (m, pc) apply apply Ĥ, cl , f Ĥ, L, Ŝ |= (m, pc) : invokevirtual M iff L (m, pc) L (m, pc + 1) pop n Ŝ(m, pc), 1 + nbArgs(M ) pop Ŝ(m, pc + 1) ∀cl ∈ top Ŝ(m, pc) , ∀m ∈ lookUp(M, cl), top Ŝ(m , Ret (m )) top Ŝ(m, pc + 1) {cl} :: pop n Ŝ (m, pc) , nbArgs(M ) L (m , 1) [0..n] nil Ŝ (m , 1) Ĥ, L, Ŝ |= (m, pc) : return iff Ŝ (m, pc) Ŝ (m, Ret (m))

  Concrete semantic values are either integers or object references. Object references are abstracted by the classes of the objects they refer to, thus, an abstract value is either a subset of the set of classes of the program P or a numerical abstraction. This means that the type Val P of abstract values de-State P = Heap P × methodName P × progCount P → LocalVar P × methodName P × progCount P → Stack P

	pends on the program P being analysed. This is an example of a dependency
	that it is important to make explicit because it ensures the finiteness of the
	abstract domain which would otherwise have an infinite number of subsets
	of classes. The abstract domain of local variables is another example of an
	abstract domain that depends on the actual program being analysed (namely,
	on the number of local variables of the program).
	For each program point in P , of the form (methodName P × progCount P ), the
	local variables (resp. the operand stack) are abstracted by an array of type
	LocalVar P (resp. a stack of type Stack P ) of abstract values. Then, the abstract
	state domain:
	contains an over-approximation of all possible concrete heaps 1 and, for each
	program point, an over-approximation of the local variables and of the operand
	stack. These approximations are formalised by a relation ∼ that connects the
	concrete domains of the operational semantics and the abstract domains. In
	logical terms, s ∼ a if a is a property of s. In set-theoretic terms, s ∼ a if
	s is a member of the set of states described by a. The formal definition of
	the ∼ relation can be found in the Appendix. Here, we only give an intuitive
	description:

  = product array[className P ] array[methodName P ] array[methodName P ] array[fieldName P ] array[progCount P ] array[progCount P ]

	Val	array[varName P ]	stack
		Val	Val
	where
	Val =	sum
	finiteSet[className P ]	lattice of integer constants

Fig. 2. The lattice of abstract states (each xX P represents the number of distinct xX elements in program P ).

The precise descriptions of the concrete and abstract heap domains are not essential for understanding the rest of the paper; they can be found in the Appendix.

Cognoscenti will know that the Coq extraction mechanism is not able to extract computational content of inductive definition made in the sort Prop.

This script simulates the standard Coq inversion tactic for inductive datatypes.

Object Ĥ (class(o))