Vincent Lesieur
email: vincent.lesieur@supagro.fr

Jean-François Martin

Hariet L Hinz

Boris Fumanal

Rouhollah Sobhian

Marie-Claude Bon

Implications of a phylogeographic approach for the selection of Ceutorhynchus assimilis as a potential biological control agent for Lepidium draba

Keywords: Invasive weed, Heart-podded hoary cress, Root-galling weevil, Host race, Genetic diversity, COI gene

The root-galling weevil, Ceutorhynchus assimilis Paykull (Coleoptera, Curculionidae), has been selected as one of the candidates to control Lepidium draba L. (Brassicaceae), a highly invasive weed in western North America. Originally been described as oligophagous, also attacking crop species, previous studies indicated that a specific host race to L. draba exists in C. assimilis. We therefore explored the evolutionary history and phylogeographic structure of this weevil by sampling individuals from 67 populations, spanning 12 countries and five different host plant species including L. draba. To explore the genetic diversity of C. assimilis, we analysed the COI gene sequences of 458 individuals. Analysis revealed three distinct evolutionary lineages, one of which, the so-called Lepidium host race, was only found on L. draba and appears to occur in a restricted geographic area, ranging between northern Spain and northern Italy. These results allow us to targeting sites for collection of the Lepidium host race and justify the prioritization of C. assimilis Lepidium host race as a candidate for the L. draba biological control.

Introduction

Heart-podded hoary cress, Lepidium draba L. ssp. draba [= Cardaria draba (L.) Desv.] (Brassicacae), is a perennial rhizomatous weed, introduced to the US as a contaminant of seed shipments from Eurasia in the late 19th century [START_REF] Gaskin | Invasion of Lepidium draba (Brassicaceae) in the western United States: distributions and origins of chloroplast DNA haplotypes[END_REF]Hinz et al., 2012). The species has since spread throughout North America and is especially problematic in the West, where it is a declared noxious weed in 15 US states, three Canadian provinces, and also in Mexico [START_REF] Rice | Invaders database system[END_REF]USDA-NRCS, 2016). Lepidium draba competes with native plants, decreasing local biodiversity [START_REF] Francis | The biology of Canadian weeds. 3. Lepidium draba L., L. chalepense L., L. appelianum Al-Shehbaz (updated)[END_REF][START_REF] Puliafico | Native and exotic grass competition with invasive hoary cress (Cardaria draba)[END_REF]. Besides its ecological impact, it causes economic losses by invading several crops [START_REF] Mcinnis | Heart-podded hoary cress[END_REF][START_REF] Mulligan | The biology of Canadian weeds. 3. Cardaria draba, C. chalepensis, and C. pubescens[END_REF] where it also poses a dual problem: as well as being a weed, it provides an alternative food source for major crop pests, such as the cabbage seedpod weevil, Ceutorhynchus obstrictus (Marsham) [START_REF] Dosdall | Developmental biology of the cabbage seedpod weevil, Ceutorhynchus obstrictus (Coleoptera: Curculionidae), in spring canola, Brassica napus, in western Canada[END_REF][START_REF] Fox | Reproductive biology of Ceutorhynchus obstrictus (Coleoptera: Curculionidae) on wild and cultivated Brassicaceae in southern Alberta[END_REF]. Furthermore, the weed, which is well adapted to sub-irrigated pastures and rangelands, is toxic to cattle due to alkaloid compounds, thus becoming a serious problem for livestock and forage production [START_REF] Francis | The biology of Canadian weeds. 3. Lepidium draba L., L. chalepense L., L. appelianum Al-Shehbaz (updated)[END_REF][START_REF] Mcinnis | Heart-podded hoary cress[END_REF].

The invasive success of L. draba is related to its vegetative reproduction by an extensive rhizome system as well as its high seed production [START_REF] Francis | The biology of Canadian weeds. 3. Lepidium draba L., L. chalepense L., L. appelianum Al-Shehbaz (updated)[END_REF][START_REF] Mcinnis | Heart-podded hoary cress[END_REF][START_REF] Mulligan | The biology of Canadian weeds. 3. Cardaria draba, C. chalepensis, and C. pubescens[END_REF]. The use of herbicides is costly, not always feasible and mechanical control is not effective due to the extensive underground rhizome system of the weed [START_REF] Miller | Plant development, water relations, and carbon allocation of heart-podded hoary cress[END_REF]. These limitations have motivated the exploration of alternative methods, and a classical biological control project was started in 2001 [START_REF] Anonymous | Whitetop / Hoary Cress[END_REF].

Among the known natural enemies of L. draba in its native range in Eurasia, Ceutorhynchus assimilis Paykull, 1792[syn. Ceutorhynchus pleurostigma (Marsham 1802)] (Coleoptera, Curculionidae) [START_REF] Colonnelli | The Ceutorhynchinae types of I.C. Fabricius and G. von Paykull (Coleoptera: Curculionidae)[END_REF] has been prioritized as a of candidates for biological control (Fumanal et al., 2004a;2004b;[START_REF] Hinz | Biological control of whitetops, Lepidium draba, L. chalepense and L. appelianum[END_REF][START_REF] Hinz | Biological control of whitetops, Lepidium draba, L. chalepense and L. appelianum[END_REF][START_REF] Virag | Phenology and temperature-dependent development of Ceutorhynchus assimilis, a potential biological control agent for Lepidium draba[END_REF]. Adults lay most of their eggs in young and soft roots of the plant, causing the development of galls in which the three larval instars of the weevil develop before larvae leave the galls and pupate in the soil [START_REF] Hoffman | Faune de France[END_REF]. Across its Eurasian distribution, the weevil has been assumed to display a broad host range and is listed as a pest of more than 13 plant species including crops [START_REF] Dennis | Agricultural insect pest of temperate regions and their control[END_REF][START_REF] Hoffman | Faune de France[END_REF][START_REF] Jourdheuil | Ceutorhynchus pleurostigma Marsham[END_REF]. However, Fumanal et al. (2004b) proposed that C. assimilis is probably a complex of morphocryptic entities that differ in their host-plant spectrum within the family Brassicaceae and one of these is a specialist on L. draba with a distribution in the warmer climatic regions of southern Western Europe (Fumanal et al., 2004a). Whilst the host-specificity and life-cycle of this specialist entity have been studied (Fumanal et al., 2004b;[START_REF] Hinz | Biological control of whitetops, Lepidium draba, L. chalepense and L. appelianum[END_REF][START_REF] Virag | Phenology and temperature-dependent development of Ceutorhynchus assimilis, a potential biological control agent for Lepidium draba[END_REF], population genetic structure and the evolutionary relationships between it and the others remain poorly depicted.

Investigating the population genetic structure of potential candidate agents at the onset of biological control programs would streamline host-specificity testing of differentiated genetic groups of the agent and hence can help improve the safety and success of biological control of weeds [START_REF] De Biase | Genetic and morphological studies of Trichosirocalus species introduced to North America, Australia and New Zealand for the biological control of thistles[END_REF][START_REF] Gaskin | Applying molecular-based approaches to classical biological control of weeds[END_REF][START_REF] Rauth | The benefits of pre-release population genetics: a case study using Ceutorhynchus scrobicollis, a candidate agent of garlic mustard, Alliaria petiolata[END_REF][START_REF] Rector | DNA fingerprinting to improve data collection efficiency and yield in an open-field host-specificity test of a weed biological control candidate[END_REF].

The aims of the current study were to further elucidate the genetic diversity of C. assimilis across its native range and between different host plants, to better characterize the distribution of the different lineages or host races and to reconstruct its evolutionary history. To do so, extensive sampling was carried out across the weevil's native range, with samples collected from different known host-plants of C. assimilis. Preliminary sampling (the one used in Fumanal et al., 2004a) was enriched with new populations collected in eastern and continental Europe, but also with more individuals analyzed per population, especially those associated with L. draba.

The samples were used to analyze the genetic structure of C. assimilis by examining the mitochondrial cytochrome c oxidase subunit I (COI) gene, a marker that has proven its usefulness and is widely used in biological control programs [START_REF] Cheyppe-Buchmann | Molecular characterization of Psyttalia lounsburyi, a candidate biocontrol agent of the olive fruit fly, and its Wolbachia symbionts as a pre-requisite for future intraspecific hybridization[END_REF][START_REF] De Biase | Genetic and morphological studies of Trichosirocalus species introduced to North America, Australia and New Zealand for the biological control of thistles[END_REF][START_REF] Nadel | Mitochondrial DNA diversity of Cleruchoides noackae (Hymenoptera: Mymaridae): a potential biological control agent for Thaumastocoris peregrinus (Hemiptera: Thaumastocoridae)[END_REF][START_REF] Rauth | The benefits of pre-release population genetics: a case study using Ceutorhynchus scrobicollis, a candidate agent of garlic mustard, Alliaria petiolata[END_REF][START_REF] Tavares | Phylogeography of the ladybird Iberorhyzobius rondensis, a potential biological control agent of the invasive alien pine bast scale Matsucoccus feytaudi[END_REF]. The results were expected to provide essential information which would help to make decision regarding the suitability of the weevil as a biocontrol agent of L. draba, and in particular for selecting areas where the most-appropriate L. draba host race should be collected for further host specificity studies. 1). By combining host-plants and geographic collection sites, the study included no less than 67 populations.

Materials and Methods

Insect sampling

Between one and ten individuals from each population were analyzed. However, for some populations of interest, up to 28 individuals were analyzed.

Molecular characterization protocol

Genomic DNA was extracted from 458 individuals using a modified cetyltrimethyl ammonium bromide (CTAB) method [START_REF] Doyle | A rapid DNA isolation procedure for small quantities of fresh leaf tissue[END_REF]) and more recently using Qiagen DNeasy Blood & Tissue kit following manufacturer's protocol.

To explore intraspecific diversity, the COI mitochondrial gene was partially amplified (831 bp) with the primers C1-J-2183 (5'-CAACATTTATTTTGATTTTTTGG-3') and TL2-N-3014

(5'-TCCAATGCACTAATCTGCCATATTA-3') [START_REF] Simon | Evolution, weighting, and phylogenetic utility of mitochondrial gene sequences and a compilation of conserved polymerase chain reaction primers[END_REF]. The PCR reaction mix contained, 1X Qiagen buffer, 0.2 µM of each dNTP, 0.3 µM of each primer and 2 U of Taq polymerase and 2 µL of genomic DNA diluted at 1/5 in a final volume of 25 µL. PCR were performed using the following program: 94°C for 3 min, followed by 35 cycles of 92°C for 30 s, 52°C for 30 s and 62°C for 1 min and finished by a final elongation at 62°C for 7 min. The amplicons were purified and sequenced in both directions by Genoscreen (Lille, France) using an ABI PRISM 3730XL DNA sequencer. Sequences were assembled into consensus contigs with CodonCode Aligner (www.codoncode.com) and then aligned using CLUSTAL W. In addition, sequences of closely related weevil species (i.e. other Ceutorhynchus species) were identified by a NCBI BLAST search in GenBank with one of the newly derived COI sequences of C. assimilis. Three COI sequences of two species (C. obstrictus, GenBank accession number: DQ058695 and JN163956; C gallorhenanus, GenBank accession number: DQ058700) were included as outgroups in the phylogenetic analysis.

Phylogenetic analysis and divergence time estimation

Relationships among C. assimilis from different host plants and geographical regions were reconstructed using both maximum likelihood and Bayesian inferences. First, jModelTest2 [START_REF] Darriba | jModelTest 2: more models, new heuristics and parallel computing[END_REF] was used to test for the best-fit model of sequence evolution. The best-fit model was selected using the corrected Akaike Information Criterion (AICc) [START_REF] Darriba | jModelTest 2: more models, new heuristics and parallel computing[END_REF]. Maximum likelihood analyses were conducted with PhyML v3.0 [START_REF] Guindon | New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0[END_REF]. Nodal support was assessed using non-parametric bootstrapping (1,000 replicates). Bayesian phylogeny was reconstructed using the software BEAST v1.8.0 [START_REF] Drummond | Bayesian phylogenetics with BEAUti and the BEAST 1.7[END_REF]. We also used this software to estimate divergence time of lineages characterized within C. assimilis. In the absence of geological and ⁄ or fossil calibration points to estimate divergence times, we dated the clock-like COI phylogeny by applying a global mutation rate of 3.54% Myr -1 , a substitution rate calibrated for tenebrionid beetles [START_REF] Papadopoulou | Revisiting the insect mitochondrial molecular clock: the mid-Aegean trench calibration[END_REF]. We used an uncorrelated lognormal (UCLN) relaxed clock under exponential growth population models. The analyses were performed using two independent runs of 20 million generations and trees were sampled every 1,000 iterations. Input files were generated with BEAUTi [START_REF] Drummond | Bayesian phylogenetics with BEAUti and the BEAST 1.7[END_REF] v1.8.0. After checking for the effective sampling sizes (ESS) of parameters (a threshold of 200 was used) with Tracer v1.6 (available from http://tree.bio.ed.ac.uk/software/tracer), the first 25% of each run was discarded as burn-in phase for the estimation of the consensus topology and the computation of the posterior probability (PP) for each node. The intraspecific relationships might be better visualized with networks, allowing a more detailed display of population information than on evolutionary trees [START_REF] Posada | Intraspecific gene genealogies: trees grafting into networks[END_REF] although both may be informative. A haplotype network was constructed in PopART [START_REF] Leigh | POPART: full-feature software for haplotype network construction[END_REF] using TCS network. To visualize the spatial distribution of the different entities (e.g.

Lepidium host race versus the other lineages), the genetic diversity of the populations was plotted as pie charts on a map.

To estimate the number of molecular operational taxonomic units (MOTUs) and to explore molecular species delimitation, two different methods were used. First, we used Automatic Barcode Gap Discovery (ABGD) developed by [START_REF] Puillandre | ABGD, Automatic Barcode Gap Discovery for primary species delimitation[END_REF]. This tool uses pairwise distance to detect a barcode gap, this barcode gap is used as a threshold to separate the sequences into putative species (i.e. genetically homogeneous groups). The procedure is recursively applied to the previously obtained groups until no more partitioning can be done. The analysis was conducted through uploading a sequence alignment on the ABGD web server at http://wwwabi.snv.jussieu.fr/public/abgd/abgdweb.html. We computed a matrix of pairwise distances using the K2P model [START_REF] Masson | A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences[END_REF] and ABGD was run with the default settings (Pmin = 0.001, Pmax = 0.1, Steps = 10, X (relative gap width) = 1.5, Nb bins = 20). The Poisson tree processes (PTP) model for species delimitation [START_REF] Zhang | A general species delimitation method with applications to phylogenetic placements[END_REF] was also used. This model uses coalescence theory and estimates the speciation rate directly from the number of substitutions. It assumes that each substitution has a small probability of generating a speciation event. Consequently, the number of substitutions between species is expected to be significantly higher than within species. The ML phylogeny obtained with PhyML was used as input. The analysis was run on a web server for PTP (available at http://species.h-its.org/ptp/) with 200,000 MCMC generations, a thinning value of 100 and a burn-in of 25%. As recommended by the developers, the convergence of the MCMC chain was confirmed visually.

To estimate divergence between the main genetic entities defined by the resulting phylogenetic tree, we used Mega version 7.0 [START_REF] Kumar | MEGA7: Molecular Evolutionary Genetics Analysis version 7.0 for bigger datasets[END_REF]. We calculated the pairwise genetic p-distances among the phylogenetic entities. To get a rough overview of the historical demography for each lineage, the frequency-based indicators of a population expansion (or selection in non-neutral markers) Fu's Fs [START_REF] Fu | Statistical tests of neutrality of mutations against population growth, hitchhiking and background selection[END_REF] were calculated with Arlequin 3.5 [START_REF] Excoffier | Arlequin suite ver 3.5: a new series of programs to perform population genetics analyses under Linux and Windows[END_REF]). Fu's statistic is considered highly sensitive to detect population expansion [START_REF] Fu | Statistical tests of neutrality of mutations against population growth, hitchhiking and background selection[END_REF][START_REF] Ramos-Onsins | Statistical properties of new neutrality tests against population growth[END_REF]. The values of Fu's Fs are expected to have significantly negative values for population expansion.

The estimation of gene diversity (H d ) and nucleotide diversity (π) for each of the sampling locality was conducted with Arlequin 3.5 [START_REF] Excoffier | Arlequin suite ver 3.5: a new series of programs to perform population genetics analyses under Linux and Windows[END_REF] and allelic richness (r) was computed using the rarefaction method proposed by [START_REF] Petit | Identifying populations for conservation on the basis of genetic markers[END_REF] using Contrib (http://www.pierroton.inra.fr/genetics/labo/Software/Contrib/).

Finally, to analyze the genetic structure among populations and to identify potentially distinct units within the restricted area where the weevil Lepidium host race was found (see Results), we used a spatial analysis of molecular variance (SAMOVA) with SAMOVA 1.0 [START_REF] Dupanloup | A simulated annealing approach to define the genetic structure of populations[END_REF].

This approach was thus only used for individuals collected on L. draba. It defines groups of populations that are geographically homogeneous and maximally differentiated. The program was run for two to 10 differentiated groups (K = 2 to K = 10) using 10,000 permutations from 100 random initial conditions.

Results

The 458 sequenced individuals from 67 populations yielded a final alignment of 774 bp long uncovering a total of 66 haplotypes. All haplotype sequences were deposited in GenBank (accession numbers: KY486382-KY486447). From the final alignment, a total of 59 (7.6%) polymorphic nucleotide sites, of which 46 were parsimony-informative. Total gene diversity was 0.929 ± 0.006 and nucleotide diversity was 0.013 ± 0.003.

The most appropriate model of COI sequence evolution was TN93+I+G, and this model was employed for further analyses. Phylogenetic reconstructions using both ML and BI revealed three divergent genetic entities within C. assimilis (Fig. 1). The first of them, referred to hereafter as the 'Lepidium host race', was defined with strong support (BS = 94 and PP = 1.00). This evolutionary lineage, composed of 12 haplotypes, was represented by weevils sampled only on L. draba ssp. draba within a restricted area comprising northern Spain, southern France and the northwestern part of Italy (Figs. 2 and3). The second evolutionary lineage, called Lineage 2 (support values: BS = 83 and PP = 0.99), was composed of seven haplotypes (Fig. 1). These haplotypes were recovered in southern

France, northern Italy and Greece from individuals collected on three different host plants: D.

erucoides, S. arvensis and B. oleracea (Figs. 2 and3). This lineage was never found on L. draba in our study. The remaining haplotypes clustered in Lineage 1 (Fig. 1). This evolutionary lineage was widely distributed across the entire sampled area and from the whole spectrum of host plants considered in this study (Fig. 3). On internal nodes, phylogeny is not fully resolved with low support values or discrepancy between ML and BI (Fig. 1).

As observed on the phylogenetic tree, the haplotype network also revealed a clear split between the Lepidium host race and the two other lineages (Fig. 3). The haplotype network showed that the Lepidium host race and Lineage 1 differed from each other by at least 14 mutation steps (Fig. 2).

The genetic divergence between sequences obtained from the Lepidium host race and the two other lineages were 2.41% and 2.21%, respectively for Lineage 1 and Lineage 2 (Table 2). This is much lower than divergence values obtained with the Ceutorhynchus species used as outgroups (11.38 -12.95%). From the ABGD analysis, the partitions 1-3 (P = 0.001000-0.002783) matched the phylogenetic tree and partitioned the dataset into three molecular operational taxonomic units (MOTUs) corresponding to Lineage 1, Lineage 2 and Lepidium host race. However, ABGD results did not fully support a marked barcoding gap (Supplementary material Fig. 1). The partition 4

(P = 0.004642) only resulted in two MOTUs while the partition 5 (P = 0.007743) suggested that C.

assimilis was a single species. The PTP analysis resulted in partitioning C. assimilis into two MOTUs, the Lepidium host race on the one hand and the combination of the Lineages 1 and 2 on the other hand.

This analysis suggested that these MOTUs may represent potential cryptic species or subspecies within C. assimilis.

Estimation of time divergence was made for the two major splits within the C. assimilis tree (Fig. 1). Divergence between the Lepidium host race and the other lineages of C. assimilis (labeled with Roman numeral I on Fig. 1) was estimated to have occurred 1.17 Mya (95% HPD: 0.70-1.76), this estimation dates the split between the lower and the mid-Pleistocene. The Lineage 1 and Lineage 2 (referred on Fig. 1 as the Roman numeral II), diverged from each other around 0.87 Mya (95% HPD: 0.50-1.26). Demographic analyses suggest a population expansion in the three lineages (Table 2), although for the Lineage 2, negative value of Fu's Fs was not significant.

Most populations within sampling localities had one to three haplotypes. Haplotype H 21, belonging to Lineage 1, was the most common and the most widespread haplotype. It was found in 83 individuals from 17 sampling sites, distributed from France to Armenia. In the restricted area where the Lepidium host race was found, the most geographically widespread haplotype corresponded to H 1, and was found in 10 sampling sites (n = 35 individuals), and only on L. draba. Both genetic diversity and nucleotide diversity varied considerably from one sampling site to another in the restricted area of the Lepidium host race as well as in the other parts of Europe (Table 1).

Within the restricted area where the Lepidium host race lineage was found, and taking into account only the weevils collected on L. draba, the SAMOVA analysis suggested the presence of five clusters in the dataset. This configuration was retained because the largest increase in FCT values was observed when the geographic sampling area was partitioned into five clusters (Supplementary material Fig. 2), although the F CT values still slowly increased after K = 5, probably a response to the continuous decrease in F SC until all sampling sites are separated [START_REF] Dupanloup | A simulated annealing approach to define the genetic structure of populations[END_REF]. Moreover, for K > 5, the newly formed groups only contained single populations, which indicates that the group structure disappeared [START_REF] Magri | A new scenario for the Quaternary history of European beech populations: palaeobotanical evidence and genetic consequences[END_REF]. The five groups were geographically consistent, except group 4 that showed a disjunctive distribution, occurring mainly in France and Northern Spain but also in Northern Italy (Fig. 4). The population A84, located in Central Spain was mostly composed of individuals harboring the haplotype H55 that is only found in this sampling site (n = 26). This population was segregated from the other Spanish populations and considered as a distinct group (group 5). Group 1, located in the northern continental range, clustered the sites A83 and A69. Those two sites are predominantly composed of individuals from the generalist Lineage 1 (Fig. 3), 14 individuals among 20 for site A83 and 12 individuals among 14 for site A69, respectively.

Discussion

Evolutionary history of C. assimilis

The results presented here, confirm the proposal [START_REF] Fumanal | High through-put characterization of insect morphocryptic entities by a non-invasive method using direct-PCR of fecal DNA[END_REF]Fumanal et al., 2004b) that the weevil populations developing on L. draba in a restricted area of the western Mediterranean region should be considered as a Lepidium host race. Present results met most of the criteria proposed by [START_REF] Drès | Host races in plant-feeding insects and their importance in sympatric speciation[END_REF] in their definition of host race including genetically differentiated sympatric populations living on different hosts. Indeed, the lineage referred to here as the Lepidium host race represents a divergent evolutionary lineage strictly associated with L. draba. The genetic divergence between the host race and the other lineages of C. assimilis (2.21% with Lineage 1 and 2.41% with Lineage 2) corresponds to values lower than those usually observed between Ceutorhynchus species (Laffin et al., 2005a) as confirmed by the divergence observed with the congeneric species used as outgroups. However, the level of divergence detected here is in the same order of magnitude as the one observed between two sister species, C. erysimi and C. contractus [START_REF] Stepanović | Morphology versus DNA barcoding: two sides of the same coin. A case study of Ceutorhynchus erysimi and C. contractus identification[END_REF]. Likewise, although the ABGD procedure tends to consider the three different lineages as a single species, the PTP analysis suggests that the Lepidium host race may potentially represent cryptic species or subspecies. The potential for hybridization between the different genetic entities has never been investigated in the field, and only partly in lab conditions (Fumanal et al. 2004a).

Preliminary crossing experiments between individuals of C. assimilis from the Lepidium host race and individuals reared from L. draba but belonging to the generalist Lineage 1 showed an absence of prezygotic barriers but suggested partial postzygotic barriers. Indeed, fertilization seemed possible and egg laying from females was observed in some cases but it was not possible to test for fertility of the resulting outcrossed progenies as they died before they reproduced. Crossing of individuals belonging to the Lepidium host race with individuals developing on other host plants (Lineage 2) resulted only in abnormal small galls and abortion of neonate larvae (Fumanal et al., 2004a). Taken as a whole, the available data (i.e. ecological, biological and genetic data) point to a limited gene flow between the Lepidium host race and the two other lineages. However, the extent of hybridization and gene flow between the different entities remain to be found under natural conditions.

This could be tested in the Rhone Valley, where the Lepidium host race and more generalist entities co-occur on L. draba. The recent development of microsatellite markers for C. assimilis [START_REF] Lesieur | Development and characterization of 11 microsatellite markers in the root-gall-forming weevil, Ceutorhynchus assimilis (Coleoptera: Curculionidae)[END_REF] will enable investigation of the gene flow between the different entities identified here.

The split between the Lepidium host race and the two other lineages was estimated to occur during the Pleistocene and, diversification within each lineage also started during this period. The Pleistocene and its climatic cycles, with the succession of glacial and interglacial periods, have had a great impact on species evolution and have shaped the current distribution of numerous organisms [START_REF] Hewitt | The genetic legacy of the Quaternary ice ages[END_REF][START_REF] Médail | Glacial refugia influence plant diversity patterns in the Mediterranean Basin[END_REF][START_REF] Schmitt | Molecular biogeography of Europe: Pleistocene cycles and postglacial trends[END_REF]. The western Mediterranean distribution of the Lepidium host race suggests one (or more) refugia in Spain or the south of France, a region identified as glacial refugium for several other species [START_REF] Médail | Glacial refugia influence plant diversity patterns in the Mediterranean Basin[END_REF].

Over its wide distribution, no clear geographic structure within Lineage 1 was found in the analysis. However, several glacial refugia for C. assimilis and further expansion of both lineages are suggested. In particular, neutrality tests support the hypothesis of a recent population expansion. The current distributions of Lineage 1 and the Lepidium host race reveal a secondary contact of those lineages in the Rhone Valley. Except for the sampling site A83 located in the Massif Central, where the Lepidium host race is not the main genetic lineage, the distribution of the Lepidium host race in France matches the Mediterranean biogeographical area [START_REF] Condé | The Mediterranean biogeographical region[END_REF]. This would suggest that past but also present climatic conditions may shape the distribution of this lineage. The geographic distribution of the Lineage 2 (i.e. Greece, Southern France and also three individuals in Italy) is also consistent with southern refugia [START_REF] Médail | Glacial refugia influence plant diversity patterns in the Mediterranean Basin[END_REF]. This lineage, only found on D. erucoides, S. arvensis and B. oleracea was never associated with L. draba. It may be more widespread than illustrated by our study, but this lack of representation may be linked with the lower sampling effort on these plants at the global scale. Moreover, the moderate support values for Lineages 1 and 2 need further considerations for better resolving the evolutionary history of these two lineages.

Within the area where the Lepidium host race is present, [START_REF] Médail | Glacial refugia influence plant diversity patterns in the Mediterranean Basin[END_REF] defined several 'phylogeographical hotspots' favorable to the evolutionary divergence of different plant species. In line with this, the weevil's genetic divergence correlates with the differentiation of the European L. draba ssp draba. Fumanal et al. (2004a) found two different plant genetic lineages within the European L. draba, one restricted to Southern Europe and one widely distributed in Europe. As for C. assimilis in which the lineages were morphologically similar, a comparison of several plant traits (such as shoot density, individual shoot height) of European populations of L. draba from several regions did not reveal any differences (Hinz et al., 2012). However, the authors did not include in their study any population of the weed from the area where the C. assimilis Lepidium host race occurs. In our study, the divergence found between the Lepidium host race and the other genetic entities of C. assimilis can also be linked with biological features of weevil populations. Differences in phenology, sex ratio, cold hardiness and overwintering survival have been observed between the different entities (Fumanal et al., 2004b;[START_REF] Virag | Phenology and temperature-dependent development of Ceutorhynchus assimilis, a potential biological control agent for Lepidium draba[END_REF]. For instance, Fumanal et al. (2004b) observed in the area where the Lepidium host race is found that sympatric weevil populations on L. draba developed faster and pupation started up to two months earlier than individuals on S. arvensis. Phenological differences are an important factor in sympatric speciation or, at least, host plant or habitat specialization [START_REF] Drès | Host races in plant-feeding insects and their importance in sympatric speciation[END_REF][START_REF] Roy | Pinpointing the level of isolation between two cryptic species sharing the same microhabitat: a case study with a scarabaeid species complex[END_REF][START_REF] Santos | Genetic isolation through time: allochronic differentiation of a phenologically atypical population of the pine processionary moth[END_REF]. These biological differences could partly explain the genetic divergence between sympatric populations living on different host-plants as observed in the two sites in southern France (i.e. Q-VV-VVS and A49-L-B (Table 1)) where the weevils were collected synchronously.

Despite numerous taxonomic revisions of the genus [START_REF] Colonnelli | The Ceutorhynchinae types of I.C. Fabricius and G. von Paykull (Coleoptera: Curculionidae)[END_REF][START_REF] Colonnelli | Catalogue of Ceutorhynchinae of the world, with a key to genera[END_REF][START_REF] Hoffman | Faune de France[END_REF][START_REF] Tempère | Faune de France, Coléoptères Curculionidae Quatrième partie[END_REF], taxonomical and nomenclatural issues represent the main constraints in studying this important weevil group, as highlighted by [START_REF] Stepanović | Morphology versus DNA barcoding: two sides of the same coin. A case study of Ceutorhynchus erysimi and C. contractus identification[END_REF]. In this context, although it was not the main aim of this study, we confirmed the distinction between the cabbage seedpod weevil, C. obstrictus (Marsham) [= C. assimilis (Paykull)], a serious European pest of canola or oil seed rape, which is invasive in North America [START_REF] Dosdall | Key pests and parasitoids of oilseed rape or canola in North America and the importance of parasitoids in integrated management[END_REF]Laffin et al., 2005b), and C. assimilis [= C. pleurostigma]. [START_REF] Colonnelli | The Ceutorhynchinae types of I.C. Fabricius and G. von Paykull (Coleoptera: Curculionidae)[END_REF] determined that C. obstrictus is the correct name for the cabbage seedpod weevil, however confusion still exists in some publications where C. obstrictus is still cited as C. assimilis. Moreover, C. assimilis has been listed as a pest of several cultivated crops such as cabbage or rapeseed [START_REF] Hoffman | Faune de France[END_REF][START_REF] Jourdheuil | Ceutorhynchus pleurostigma Marsham[END_REF].

Implications for biological control

The present distinction between the specialist (i.e. the Lepidium host race) and the other lineages has serious implications from a biological control perspective. Indeed, the Lepidium host race should be considered as beneficial and a potential biological control agent for L. draba whereas the others, particularly those developing on economic crops, should still be regarded as pests. First, the results allow targeting precise sites for collection of the Lepidium host race. We showed that the Lepidium host race of C. assimilis is restricted to a relatively small geographic area. On the 122 individuals collected on L. draba within a triangular area including Valls in Cataluna (Spain), San

Remo in Ligury (Italy) and Montélimar in the Rhone Valley (France), 116 individuals (ca. 95%) corresponded to the Lepidium host race.

Secondly, within the restricted distribution area where the Lepidum host race occurs in sympatry with the other lineages, Lineage 1 was observed on L. draba at a low frequency and Lineage 2 has never been found on L. draba but on other Brassicaceae. Moreover, when sampling was carried out synchronously on several host plant species, the Lepidium host race has never been found on plants other than L. draba, thus reducing the risk of collecting generalist individuals. Indeed, these other plant species do not constitute acceptable hosts for the Lepidium host race (Fumanal et al., 2004b). Thus, when restricting sampling to sites/areas where the Lepidium host race predominates and only collecting galls/adults from L. draba, one can be close to certain to only collect individuals of the specialist Lepidium host race. Nevertheless, as previously mentioned, the different entities are morphologically identical, discriminating the Lepidium host race from the other lineages remains an issue. However, [START_REF] Fumanal | High through-put characterization of insect morphocryptic entities by a non-invasive method using direct-PCR of fecal DNA[END_REF] developed a non-invasive technique based on direct-PCR of fecal DNA combined with double strand conformation polymorphism (DSCP) typing. This method allows to quickly discriminating the Lepidium host race from the other entities without killing the insects and could be adapted for systematic screenings with current metabarcoding methods.

Thirdly, based on our results, the split between the Lepidium host race and the other more generalist lineages is relatively old (1.17 Mya, Pleistocene) suggesting that the Lepidium host race belongs to a long-standing L. draba-associated entity rather than a lineage prone to a recent host shift.

As such it should remain specific to L. draba, which justifies its prioritization as a candidate for biological control of L. draba.

Even if the results presented here justify the prioritization of the Lepidium host race as a candidate for the L. draba biological control, studies on the biology and the specificity of the host race must be undertaken to evaluate its potential host spectrum in North America. Host specificity tests, including North American endemic plant species, are currently conducted by CABI at Délemont (Switzerland).

Genetic diversity within the Lepidium host race was highly variable from one sites to another, and in some sampling sites the genetic diversity was very low (e.g. sites A55; A69; A72 (Table 1)). At the sampling site scale, only one to three haplotypes were observed, even when the sampling size was large (n > 25). Collecting individuals from several nearby sites should ensure maximizing genetic diversity. Preserving this diversity in released populations is of importance as genetic variation in ecologically important traits is hypothesized to be important in successful establishment, allowing adaptation to the novel environment [START_REF] Dlugosch | The devil is in the details: genetic variation in introduced populations and its contributions to invasion[END_REF][START_REF] Szucs | The roles of demography and genetics in the early stages of colonization[END_REF].

Lepidium draba is invasive in a large part of North America, including areas with a wide spectrum of climatic conditions [START_REF] Rice | Invaders database system[END_REF]USDA-NRCS, 2016). A climate match model suggests that the Lepidium host race may establish and persist in some areas where the weed is problematic, while establishment in more continental climates could be possible, but more difficult [START_REF] Virag | Phenology and temperature-dependent development of Ceutorhynchus assimilis, a potential biological control agent for Lepidium draba[END_REF]. However, relatively rapid adaptation after release may occur as observed for the flea beetle

Longitarsus jacobaeae (Waterhouse) [START_REF] Szucs | Post-introduction evolution in the biological control agent Longitarsus jacobaeae (Coleoptera: Chrysomelidae)[END_REF]. Preserving the genetic variation of the Lepidium host race in released populations may increase their adaptive potential in the new environment [START_REF] Phillips | East meets west: adaptive evolution of an insect introduced for biological control[END_REF], and therefore also potential adaptation to more continental climate, such as eastern Colorado, Wyoming and central Montana.

The L. draba populations that invaded North America displayed genetic differentiation and originated from multiple Eurasian origins including the southern European region where the weevil host race occurs [START_REF] Gaskin | Invasion of Lepidium draba (Brassicaceae) in the western United States: distributions and origins of chloroplast DNA haplotypes[END_REF]. Likewise, within its restricted distribution area, the genetic diversity of the Lepidium host race appears as different units as highlighted by the SAMOVA.

Different populations of potential biological control agents may have different abilities to develop and damage different introduced genotypes of the target weed, as it was observed for the eriophyid mite,

Floracarus perrepae Knihinicki and Boczek, to control the fern, Lygodium microphyllum (Cav.) R.

Br. in Florida [START_REF] Goolsby | Matching the origin of an invasive weed for selection of a herbivore haplotype for a biological control programme[END_REF]. Because of the common pattern of differentiation between the Lepidium host race of C. assimilis and L. draba, future investigations should evaluate the impact of the different units of the Lepidium host race on different populations of L. draba, including North American populations. Color codes of the populations correspond to the five groups identified by SAMOVA. Table 1. Sampling details and summary statistics of genetic diversity of the sampled Ceutorhynchus assimilis populations used in this study. Table 2. Estimates of evolutionary divergence over the different genetic entities (p-distance, expressed as a %) and results of neutrality tests for the three lineages identified within Ceutorhynchus assimilis.

Figures and Tables Caption

  Galls containing mature larvae of C. assimilis were collected in the field between 2001 and 2014 from the five taxa within the Brassicaceae known to be the most commonly attacked by the weevil: L. draba (n = 366), Brassica oleracea L. (n = 52), Brassica napus L. (n = 7), Diplotaxis erucoides Dc. (n = 35) and Sinapis arvensis L. (n = 18). Plants were sampled at least 1 m apart and only one larva per gall and per plant was collected. Some of the larvae were reared to adult for morphological confirmation by Enzo Colonnelli (University of Rome, Italy). The others were stored in absolute ethanol at -20°C until DNA extraction. Sampling covered a large part of the Eurasian distribution of C. assimilis and collection sites were distributed across 12 countries (Table

Fig 1 .

 1 Figures and Tables CaptionFig 1. Bayesian phylogenetic tree from analysis of the COI sequences of Ceutorhynchus assimilis. Maximum likelihood bootstrap values (> 80%) are listed above the branches, followed by Bayesian posterior probabilities (> 0.75). Branch lengths represent expected substitutions per site. The scale bar indicates the expected number of substitutions per site. Ceutorhynchus obstrictus and C. gallorhenanus were used as outgroup. Roman numerals refer to estimated divergence times given in the Results section. Grey vertical bars represent the results of the species delimitation methods (i.e. ABGD[START_REF] Puillandre | ABGD, Automatic Barcode Gap Discovery for primary species delimitation[END_REF] and PTP[START_REF] Zhang | A general species delimitation method with applications to phylogenetic placements[END_REF] procedures). Fig 2. COI mitochondrial haplotype network of Ceutorhynchus assimilis. Each circle corresponds to one haplotype; circle size gives the proportion of individuals belonging to the haplotype. The color inside each circle represents the host and indicates the proportion of individuals sampled in the different hosts. Small crossing lines indicate the number of mutations separating haplotypes. Black circles represent missing intermediate haplotypes. Fig 3. Geographic distribution of the different lineages of Ceutorhynchus assimilis. Pie chart sizes are proportional to sample size. Fig 4. Geographical distribution of the five SAMOVA derived groups identified within the 23 populations of the Lepidium host race of Ceutorhynchus assimilis in the western Mediterranean region.Color codes of the populations correspond to the five groups identified by SAMOVA. Table1. Sampling details and summary statistics of genetic diversity of the sampled Ceutorhynchus assimilis populations used in this study. Table2. Estimates of evolutionary divergence over the different genetic entities (p-distance, expressed as a %) and results of neutrality tests for the three lineages identified within Ceutorhynchus assimilis.

Acknowledgements

We thank the Director of EBCL, Lincoln Smith, for reviewing the manuscript and providing useful comments. We thank Camille Rouvière for her help in extracting DNA and sequencing. We also thank Fatiha Guermache and Mélanie Jeanneau (USDA-ARS-EBCL) for technical assistance and field collections. We are also indebted to many collaborators who provided samples. Enzo Colonnelli (University of Roma, Italy) is gratefully acknowledged for identification of the weevils. We would also like to thank Dr. G. Kergoat (INRA, UMR CBGP) for helpful discussions on data analyses and interpretation. Mention of any trade names or commercial products in this publication is done solely for the purpose of providing specific information, and does not imply recommendation or endorsement by the USDA; the USDA is an equal opportunity provider and employer. This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.


Dr Fridtjof Siebert
email: siebert@aicas.com

Static Data Flow Analysis for Realtime Java Runtime Error Detection *

Keywords: program analysis, data-flow analysis, Java, Real-Time Specification for Java, context sensitive, pointer analysis, runtime errors

The strict and clear semantics of Java make it an ideal language for static analysis. Nevertheless, the use of programwide pointer analysis for proving the absence of Java runtime error conditions such as null pointer uses or illegal array indices is still not widespread. Current uses of program-wide pointer analysis focus on extracting information for optimisations in compilers. In this case, imprecise analysis results only in less agressive optimisation, which is often tolerable.

Existing implementations of program-wide data flow analysis either lack the required accuracy to prove the absence of large enough numbers of certain errors or cause an explosion in analysis time and space requirements for non-trivial applications. Low accuracy leads to large numbers of "false positives", i.e., code for which the analysis fails to prove that a certain error condition does not occur. An explosion in the analysis effort causes the analysis not to produce any useful results within reasonable time at all.

The approach presented in this paper applies the analysis to create a correctness proof of safety-critical Java applications. This includes the absence of runtime errors (null pointer use, division by zero, etc.), the absence of potential deadlocks, the correctness of region-based memory management and the determination of resource constraints (heap and stack use).

INTRODUCTION

The enormous success of Java technology is due to the language's many advantages over more traditional languages, such as higher productivity and safety. Even critical applications, as in automotive or aerospace control, can profit from these advantages hidoors, aero [START_REF] Hidoors | High Integrity Object-Oriented Realtime Systems[END_REF][START_REF] Aero-Vm | the hard realtime virtual machine for onboard space systems[END_REF]. Extensions such as the Real-Time specification for Java (RTSJ) [START_REF] Bollela | Real-Time Specification for Java[END_REF] or real-time garbage collection technology [13] make Java implementations fit for the time-critical application domain.

Scoped Memory in the RTSJ

Language extensions such as the Realtime Specification for Java [START_REF] Bollela | Real-Time Specification for Java[END_REF] have made it possible to use Java implementations even though a garbage collector may interrupt the execution of normal Java code in an unpredictable way. Region based memory management [START_REF] Tofte | Region-based memory management[END_REF] using scoped memory and realtime tasks that cannot access the garbage collected heap make it possible to develop code that has predictable timing behaviour and that can be used for hard realtime tasks.

Scoped memory provides an allocation context that is freed when the context is exited. The use of scoped memory, however, requires that certain runtime error conditions are avoided. These new runtime error conditions are scopes that are nested improperly and assignment that may lead to dangling references.

Scoped memory areas may be nested such that entered memory areas form a tree. Each scope has at most one parent scope in this nesting, but it may have several child scopes. Since the same scoped memory area may be used by different threads simultaneously, each thread must follow the same nesting order. Current implementations of the RTSJ check at runtime that the scopes actually form a proper tree and not a cyclic graph. If a cycle would be created by entering a scoped memory area, a ScopedCycleException is thrown at runtime. Since memory allocated in a scope will be reclaimed after this scope was exited by all threads, the implementation has to ensure that no dangling references to any objects allocated in a scope will exist when this scope is exited. Therefore, the RTSJ does not permit storing a reference to an object allocated in scoped memory into a static variable or into another object that was allocated in heap memory, immortal memory, or in an outer scope. Current implementations of the RTSJ use runtime checks on all pointer assignments to make sure that no assignments that may lead to dangling references are made. In case an attempt is made to make such an illegal assignment, an IllegalAssignmentError is thrown by the virtual machine.

In addition to ScopedCycleException and IllegalAssignment-Error, another runtime error that may occur when using scoped memory is, of course, an OutOf M emoryError when more memory is allocated than the scope was declared to hold.

Pointer Analysis

The application of pointer analysis to object-oriented languages such as Java is a relatively new area of research. There are two main uses of the results of pointer analysis: the results can be used to control optimisations of code manipulating tools such as compilers, or the results may be used for the correctness analysis of an application. In the presented approach, the results are used for correctness analysis, which requires a very accurate analysis to produce useful results.

Contributions

This paper presents a context-sensitive and flow-sensitive pointer analysis algorithm for an object-oriented environment. The results of this pointer analysis are applied to prove the absence of error conditions. The development of the analysis algorithm was driven by the requirement to reduce the number of false positives in the set of potential errors that is reported without causing a state explosion. The error conditions include standard Java runtime errors such as null pointer use, illegal casts and illegal array stores, but also memory related runtime errors in applications using the Real-Time Specification for Java [START_REF] Bollela | Real-Time Specification for Java[END_REF]. The analysis results are used for the verification of safety-critical Java applications that are developed according to the profiles defined within the HIJA project [START_REF] Hija | High-Integrity Java[END_REF].

To illustrate the usefulness and scalability of the presented algorithm, it is applied to the real-world Java applications that are part of the SPECjvm98 benchmark suite [START_REF]SPEC JVM89 Benchmarks[END_REF], the time and memory demands for the analysis of these applications are presented as well as the achieved analysis accuracy for runtime error conditions.

MOTIVATING EXAMPLE

A typical use of scoped memories is show in figure 1. In This example, a realtime thread runs it its own scoped memory area s1. It starts by reading data from several files. A second memory area s2 is used to store all the temporary objects required to read those files. However, the data read from the files is allocated in s2 and copied directly to s1 causing an IllegalAssignmentError at runtime in the call to V ector.add made in line 28. This kind of programming error is hard to predict since it is caused caused by an apparently harmless pointer store operation. Finding it typically requires complex manual analysis of the code to determine the possible memory areas of the source and the target of the pointer store operation. In this example, the illegal assignment error occurs inside class V ector, even though the code of class V ector is correct; the error is in the call at line 28 of the example that passes an argument that cannot be stored into the vector. This example illustrates that the feature of not causing illegal assignment errors at runtime is not an aspect of a single class or method, but an aspect of a whole application.

To prove the absence of such errors, all assignments have to be analysed in all possible calling contexts they may be used in. The pointer analysis presented in this paper solves this problem. One of the results of the pointer analysis is the value sets of all variables in the application. The representation of these values includes the memory area the values were allocated in, such that assignment errors can be found (see section 4.10).

POINTER ANALYSIS

Background

Significant effort has been undertaken in the area of pointer analysis during the last decades [START_REF] Hind | Pointer analysis: Haven't we solved this problem yet?[END_REF]. Pointer analysis typically uses static, program-wide data flow analysis, which is an iterative algorithm that determines an upper bound for the set of values each reference variable in an application may hold. In addition to the set of values for each variable, the analysis determines a set of invocations, where an invocation is a method call together with context information at the call. The resulting set of invocations is an upper bound for the set of invocations that may be performed during an actual program run.

The analysis starts with an empty set of variable values and the set of invocations containing only the main routine of the analysed application. In each iteration, the set of possible values each variable may hold is joined with the set of values that are assigned to these variables by any method that is in the invocation set. Also, any new invocation that is performed by a method that is in the set of invocations is also added to this set. The iterative analysis continues as long as these two sets grow, stopping when the smallest fix point has been reached, i.e., when the sets of values and invocations remained constant during a complete iteration over all invocations.

Pointer analysis is called context-sensitive when the context of the caller is part of the representation of invocations and values. Context information is usually the call chain that leads to an invocation. However, context may include other information such as the thread that performs the invocation or environmental information such as the current allocation context when region-based memory management is used [START_REF] Tofte | Region-based memory management[END_REF][START_REF] Tofte | A brief introduction to Regions[END_REF].

An algorithm that is not context-sensitive is called contextinsensitive. Context-insensitive pointer analysis identifies invocations and values by the method that is invoked and the source code position that creates a value, respectively. Context-insensitive analysis significantly reduces the analysis complexity, but it yields results that are not accurate enough for the purposes described in this paper: values created in different contexts cannot be distinguished and result in the inability to prove the absence of an error. For example, since the instances of a container that are used by different threads cannot be distinguished, a context-insensitive analysis cannot detect that thread local objects stored into a thread local container are not accessible by another thread that uses a different thread local container instance.

In a context-sensitive analysis, the complete call chain is usually used as context. Since this leads to infinite value sets for recursive routines, the call chain has to be reduced to contain no or only a limited number of cycles. However, even with this restriction, the number of possible call chains typically grows exponentially with the application size making context-sensitive analysis difficult to apply to real world applications.

Pointer analysis can be classified further as flow-sensitive and flow-insensitive. A flow-sensitive analysis respects the order of statements during the analysis of one routine, while a flow-insensitive analysis ignores this order. A flow-sensitive analysis achieves higher accuracy since information available in the control graph (such as a null pointer check) can be used to reduce the set of values of a variable. Unlike contextsensitivity, the effect of flow-sensitivity on the performance of the analysis is less critical; the additional overhead is similar to the overhead of routine-wide (global) data-flow analysis that is widely applied in optimising compilers at an acceptable cost.

Object-sensitive points-to analysis for Java was presented by Milanova et. al [START_REF] Milanova | Parameterized object sensitivity for points-to and side-effect analyses for java[END_REF]. In object-sensitive analysis, the context information does not consist of the call chain, but the allocation site of the current object (this in Java) is used as context information. This approach brings a significant improvement in accuracy compared to a context-insensitive analysis while the analysis complexity grows less than using a context-sensitive analysis based on the complete call chain.

Jamaica Data Flow Analysis

For the analysis of the correctness of applications using the Real-Time Specification for Java, a new pointer analysis algorithm using augmented context information has been implemented. This data flow analysis uses the intermediate code representation used by the JamaicaVM [START_REF]Jamaica virtual machine[END_REF] static Java compiler generated from Java byte code. Single instructions are more fine-grain than bytecodes. For exmaple, an array element access is split into four independent instructions that check the array for null, obtain the array length, check the index value and finally read the array element. This intermediate representation replaces the Java stack and the local variables used in the bytecode by using the static single assignment form [START_REF] Alpern | Detecting equality of variables in programs[END_REF][START_REF] Rosen | Global value numbers and redundant computations[END_REF] instead. The static single assignment form simplifies the local data flow analysis in a single method since the data flow between intermediate commands is explicit.

During the data flow analysis, two sets are determined: the set of invocations (called methods with their context) and the set reference values for each reference field and reference array's elements. The analysis runs iteratively starting with the main function of the application1 . The data flow for all invocations is analysed in each iteration. During the analysis, new values are added to the value sets of fields and array elements and new methods that are found to be called are added to the set of called methods. The algorithm terminates when these sets remained constant during one iteration.

Reference values are identified by the class of the object they represent together with context information. This context information is crucial. When it is too detailed, the number of values explodes and the analysis becomes infeasible, while too little context information results in an analysis that finds more "false positives", i.e., potential errors that actually cannot occur at run-time. The context information of the Jamaica data flow analysis consists of the allocation site, the thread that performed the allocation, the current memory area in use, the set of locks held and a form of object context as proposed by Milanova et. al [START_REF] Milanova | Parameterized object sensitivity for points-to and side-effect analyses for java[END_REF].

To reduce the analysis effort, the analysis is split into major and minor iterations. A major iteration analyses all calls in the set of called methods. For the minor iterations, the called methods are placed into separate age groups. If the analysis of a call causes the call or value set to grow, the next iteration is restricted to the methods in the same or younger age groups. This means that repeated analysis of invocations that had now effect on the analysis results are avoided in minor iterations. This analysis also distinguishes object initialisation and object use which significantly improves the analysis accuracy for object oriented applications. Specific properties such as singleton instances and embedded instances are also detected to further improve analysis accuracy. This is the output of the the analysis run on a HelloWorld application:

>jamaica -dfa HelloWorld Jamaica Builder Tool 2.9 Release 5 DFA ITERATION 1. Even though a HelloWorld is very small, the analysis has to analyse all the code that is executed during startup of the virtual machine, which leads to a total of 341 methods that in this case. Each line that is printed by the analysis shows the state after one major iteration. The analysis stabilises after 8 major iterations, while at most 27 minor iterations where needed (in major iteration 3).

During the analysis, 2332 invocations where found for 341 methods, i.e., there are 2332 different calling contexts even though there are only 341 different methods that may be called. 302 different reference values where detected and 847 different sets of these values were created to store the values of variables. The total analysis time was less than 12 seconds, a time short enough that enables regular use of the analysis tool, e.g., as part of the normal build process of an application.

APPLICATION OF POINTER ANALYSIS RESULTS

Pointer analysis results are used for four purposes: the absence of runtime exceptions such as null pointer uses and illegal casts, the correctness of synchronisation, the correctness of the region-based memory management available in the RTSJ and the determination of worst-case memory allocation and worst-case stack use.

Runtime Error Detection

The runtime errors detected by the presented analysis are null pointer dereferencing, type cast and array store errors.

null pointer usage errors

Making null a special value for references, that is traced by the data flow analysis, also enables proving the absence of null pointer dereferencing. The detection of a potential presence of a null pointer use is straightforward: At any point in the program that dereferences a pointer, if the null value is part of the value set of the dereferenced variable, there is a potential null pointer use. Since all instance and static reference fields in Java are initialised with the null value, for a useful null pointer use analysis it is essential that the presence of initialisation code that overwrites this null value is detected reliably.

Type cast errors

A type cast in Java performs a runtime check that ensures that the casted reference is assignable to the target type. If this is not the case, a ClassCastException is thrown. The availability of the exact value sets enables the detection of potential class cast exception. When for every cast the set of values that is casted contains only values assignable to the destination type, it is proven that the cast will succeed.

Array store errors

Java permits the assignment of reference arrays to array variables of a more general element type. To ensure that storing an element in an array does not store a value of an incompatible element type into an array of a more specific element type, a runtime check is performed on every array store. The following code illustrates a code sequence that causes such a runtime check to fail. With the availability of complete value sets of all variables, it is possible for each array store to check if all possibly stored values are assignable to all possible target array element types. When this is the case, no array store error may occur at runtime, otherwise the assignment is a potential error.

Array index errors

To be able to analyse the validity of an array index variable, the analysis follows integer values in a way similar to pointer values. Additionally, for each array that is used by the application, the array length provided to the array allocation expression will be saved with the array reference, such that the length will be available at all uses of exactly this reference to the allocated array. Furthermore, array accesses frequently occur using an index variable that is incremented repeatedly in a loop. For the analysis to be able to determine a useful maximum value for the index variable, loop continuation conditions of the form index < array.length must be detected by the analysis to deduce that an access of the form array[index] is legal.

With this infrastructure, the analysis is able to prove that the majority of array accesses in a typical application are correct.

Negative array size errors

With the integer values taking part in the analysis, the runtime error that would occur on the allocation or an array with a negative size can be found trivially: If the array size on any array allocation may be a negative value, such a runtime error may occur.

Division by zero errors

Divisions by zero in Java cause an arithmetic exception. The proof of the absence of such errors is trivial with the integer value ranges: Only if zero is part of the values of the divisor, a division by zero may occur.

Correctness of Synchronisation

The correctness of synchronisation in a Java application is a hard problem. Errors such as deadlocks that result from different locking orders between threads require an accurate analysis to be detected statically, while these errors occur only sporadically at runtime and are hard to reproduce.

To be able to verify the correctness of synchronisation, the notion of a thread first needs to be available in the pointer analysis. In Java, a thread is started via a call to method start on a new instance of class T hread or a subclass of T hread. When a new thread is started, the run method is called on this thread instance. This thread instance is used by the analysis to identify threads. The context of all invocations contains the thread represented by its thread instance. Whenever a call to T hread.start is detected by the analysis, a corresponding invocation of the run method using the new thread instance as thread context is added to the set of invocations.

A call to T hread.start may spawn an arbitrary number of threads if the target thread instance is not a singleton. To be able to detect thread related errors between several such threads with the same context, a second invocation of the same thread is created using a copy of the value that represents the original thread instance (the same idea is used for thread escape analysis by [START_REF] Whaley | Cloning-based context-sensitive pointer alias analysis using binary decision diagrams[END_REF]). The copy is marked with a flag isT win such that results can later be filtered appropriately.

In addition to the thread context, it is required to have information on the set of locks that a thread may hold at any point of the analysis. The context of an invocation is therefore equipped with a set of locks that the thread may hold at the invocation. Any synchronisation performed adds the objects the thread synchronises on to the set of locks that may be held at the current invocation context. Any invocation performed during the synchronised statement sequence will use this set as its synchronisation context.

Absence of deadlocks

Since the set of locks that are held at each invocation is part of the representation of invocations, the proper nesting of synchronisation can be verified straightforwardly. Potential deadlocks as the one illustrated in Figure 2 can be detected. For this deadlock detection, the order in which locks are entered is recorded for each thread. Then, it is checked if other threads that synchronise on the same values do this in exactly the same order. If other threads may synchronise on objects in a different order, there is a potential deadlock. In this case, the innermost synchronisation that may cause a deadlock is displayed as a potential error.

One important code pattern that occurs frequently in Java code is a synchronised instance method that calls another synchronised instance method as shown in Figure 3. Using the plain pointer analysis results, we will get a false positive potential deadlock reported here since it is not obvious from the pointer analysis results that check, when called from m, will synchronise on exactly the same object and hence may not cause a deadlock. The analysis therefore has been extended to detect invocations within a synchronised method that invoke another synchronised method on exactly the same target object. In this case, the inner synchronisation will be ignored.

Correctness of region-based memory management

To be able to verify the correctness of assignments of objects allocated in scoped memory and the absence of scope cycles, the context information for invocations and types is extended with the current allocation context. This allocation context is identified by the corresponding memory area instance. On a call to enter of a memory area, the context is set to that memory area for the invocation of run method that executes in this area.

Absence of cycles between scopes

Verification of the absence of scope cycles is performed by recording a ordering relation whenever a scoped memory area is entered in a context that uses another scoped memory area as a surrounding allocation context. Whenever a new relation is added to this order, DFA checks that this new relation still respects the single parent rule defined by the RTSJ. When this is not the case, a possible ScopedCycleException is reported.

Verifying assignments

The value that represents an allocated object includes the memory area context of the invocation that allocates the object. This information can then be used to check for all reference stores where an IllegalAssignmentError might occur during runtime. When the assigned reference in the store might be allocated in a memory area that is not equal to or a parent of the target of the store, then a possible IllegalAssignmentError is reported by the analysis.

When applying the analysis to the example from figure 1, the illegal assignment is detected reliably. Figure 4 shows the output of the data flow analysis tool when run on this example. The first line of the output is a summary of the problem: there is a potential illegal assignment to an array at line 530 in class V ector (at bytecode number 48). The following two lines show the assignment that causes the problem: the target of the assignment is an array allocated in class V ector at line 148, while the assigned value is a reference to a byte array allocate in line 28 of Test.java. This array resided in the scoped memory LT M emory created in line 7 of Test.java, which is the scoped memory s2. Lines 4 through 10 give the context information for the failing assignment instruction. The context is the method V ector.addElement with the allocation context being the LT M emory created in Test.java in line 7, which is s2. Line 5 shows the current thread, which is the RealtimeThread created in Test.java in line 11. Line 6 and 7 show the potential values passed to this routine. Finally, to guide the user to the source of the problem, lines 9 through 17 show an example of call chain that leads to the problem. Here, we can see that the call to V ector.add in line 28 of Test.java is on the call chain.

Since the call chain is not used as context information by the analysis becauuse this would lead to an explosion in the number of invocations, several different call chains may lead to the same invocation. This is why, for each invocation, only one example call chain is shown.

Worst-case memory usage

The accurate invocation graph that is a result of the presented analysis can be used for automatic analysis of worstcase memory demand of the threads that are part of one application. A traversal of the invocation graph and summing of the memory demand of each invocation results in the total memory demand of each method. For this analysis, however, additional constraint information on maximum recursion depths, maximum loop counts, and maximum sizes of allocated arrays is required. This information is not available from the pointer analysis. Instead, the HIJA project uses additional tools that require annotations in the source code or in separate files to provide these constraints. The correctness of these annotations needs to be verified. The HIJA team hija is investigating the use of formal verification based on the KeY verifier key03 for this.

Worst-case heap memory use

For worst case heap use, the amount of allocation needs to be summed up recursively starting from the main method of each thread. The sum of the memory allocated within loops needs to be multiplied by the maximum loop count and allocations in recursive methods can be determined by multiplying the maximum recursion depth with the allocation performed within one recursive cycle.

Worst-case stack use

The maximum stack use can be determined by an algorithm similar to the worst-case heap use, only the stack use does not need to be summed up for different calls that originate in the same method; rather it is sufficient to use the maximum stack use of all called methods. Also, stack use is independent of loop counts, but it strongly depends on maximum recursion depths. This stack use in a recursive method is the product of the stack use in one recursive cycle and the maximum recursion depth.

First experience

First experience with worst-case memory use determination show that the number of additional constraints that are required is limited such that this information can be provided manually even for moderately complex applications. The analysis itself is fast enough even for larger applications.

EXPERIMENTAL RESULTS

Performance

To measure the performance and accuracy of the presented points-to analysis, the widely applied benchmarks from the SPECjvm98 benchmark suite and a simple "Hello-World" like application were used. Even though a "Hello-World" sounds trivial, due to the complex startup code in Java even such a minimal application requires the analysis of 340 methods. The applications in the SPECjvm98 benchmark suite were not written to be easy to analyze, so they pose a much harder test to the analysis framework than the safety-critical applications for which specific coding guidelines will be developed that ease the analysis.

The performance was measured on a Mobile Intel Pentium 4 -M CPU at 1.8GHz running Linux kernel version 2.4.27 (SuSE 8.2). Figure 5 illustrates the analysis performance:

The analysis of these tests took between 5 and 710 seconds and required between 34 and 204MB of memory. The number of distinct reference values that where found during the analysis was between 326 and 2298, the number of invocations was between 1989 and 9353, the number of analyzed Java methods was between 340 and 1755.

Four tests exceeded the set analysis time budget of 30 seconds and had the accuracy of some types reduced. For jess, very frequent uses of class StringBuf f er lead to a reduction in accuracy for this class, while raytrace and mtrt have two classes ObjN ode and OctN ode that are used in too many different contexts. Somewhat exceptional is the behavior of javac, which has a complex recursive use of many different classes for expressions that cause an explosion in the analysis effort. So the accuracy was reduced for these expression classes.

The number of source code positions for which potential errors were found are illustrated in Figure 6. Between 82% and 100% of all pointer uses could be proven not to use a null pointer in these tests. For type casts, for all tests except one more than 85% of the casts could be proven not to fail at runtime, the one exception is javac where the reduction of accuracy lead to being able to verify only 40% of the casts. Very good results where achieved for array stores, at most 8% of the array stores could not be proven correct. Finally, about 66% of synchronization could be proven not to cause a deadlock.

In summary, a very high percentage of runtime error conditions could be verified with this analysis. First inspections have shown that many of the remaining false positives can be eliminated by simple coding guidelines or by enhancements of the analysis. An example is the frequent code pattern that calls a method on a field f with an explicit null check:

if (f != null) { f.m(); } This code is dangerous if null may be assigned to f by another thread. The current analysis does not record which threads perform assignments to fields, so a potential null pointer use will be reported here. A simple code restructur-ing using a local variable solves the problem:

C local_f = f; if (local_f != null) { local_f.

m(); }

Now, there is no potential null pointer use. For HIJA, we are collecting these kinds of restructuring to form coding guidelines for safety-critical applications. Of course, the approach of extending the accuracy of the analysis to cover such code without modifications in the application is also being followed.

Graphical User Interface

To improve the usability of the analysis, a graphical frontend was developed that permits browsing through the tree of source code files while potential errors detected by the analysis will be displayed. An example of this graphical output is shown in Figure 7: Here, a potential dead-lock is shown that was detected by the analysis. The displayed hierarchy starts with the packages of the application, then the classes within a package, the methods in a selected class and the method code itself. Any element that contains none of the selected error kinds will be displayed in green, while elements with potential errors are shown in orange.

RELATED WORK

Pointer analysis algorithms have been subject of research for over 25 years [START_REF] Hind | Pointer analysis: Haven't we solved this problem yet?[END_REF][START_REF] Sharir | Two approaches to interprocedural data flow analysis[END_REF]. Among the list of open issues that where identified by Michael Hind [START_REF] Hind | Pointer analysis: Haven't we solved this problem yet?[END_REF] are scalability, precision of results, addressing client's needs, and the support for Java and object oriented languages. In general, the problem is to obtain suffficient accuracy for practical use without incurring state explosion during execution.

Efficient points-to analysis implementations that scale well to real world applications were originally restricted to con-

Figure 1 :

 1 Figure 1: Example that causes an IllegalAssignmentError in line 28.

  [START_REF] Alpern | Detecting equality of variables in programs[END_REF] = "Another String" // ok 8: a[3] = new Integer(3); // error!

Figure 2 :

 2 Figure 2: Potential deadlock between two threads.

Figure 3 :

 3 Figure 3: Typical nested synchronisation pattern

Figure 4 :

 4 Figure 4: Detailed output of the data flow analysis when run on the example from figure 1.

the analysis actually starts with the virtual machine initialisation code that is called before the main method. For Ja-maicaVM, this means that an internal constructor of T hread and the static initialiser of class System is also initially added to the set of invocations

This work was partially funded by the European Commission's 6th framework program's HIJA project, IST-511718.

text-insensitive and flow-insensitive analysis. The first contextinsensitive and scalable implementation was provided by Steensgard [START_REF] Steensgaard | Points-to analysis in almost linear time[END_REF]. More recently, context-sensitive points-to analysis that scales well to large C applications has been presented by Fähndrich et al [START_REF] Fähndrich | Scalable context-sensitive flow analysis using instantiation constraints[END_REF][START_REF] Foster | Polymorphic versus monomorphic flow-insensitive points-to analysis for c[END_REF]; however, these approaches are either flow-insensitive or unification based. A unification based algorithm regards assignments as bidirectional such that the source and target variable of an assignment has the same value set, which leads to significantly reduced precision compared to the inclusion based approach that is presented here. Furthermore, these earlier approaches differ from the presented approach in that they are not fieldindependent, whereas the approach presented here maintains separate value sets for each field.

CONCLUSION

The presented pointer analysis can prove the absence of pointer and integer related errors such as null pointer use or array index errors, but also errors related to the use of region based memory management using the mechanisms available in the Real-Time Specification for Java. The analysis serves as a basis for worst-case memory use analysis enabling static analysis to avoid resource related runtime errors. This is of particular interest for safety-critical code that needs to be certified.

It has been shown that this approach scales well to medium size real-world applications and can prove the correctness of a high percentage of statements that are potential sources of runtime errors.

Future work needs to focus on the development of coding guidelines that ensure a more accurate analysis and that avoid certain obvious problems. Also, enhancements in the analysis accuracy may be achieved by recording additional information such as the set of threads that modify a field.