Katharina E Effenberger

Elin Borgen

Christine Zu Eulenburg

Kai Bartkowiak

Andrea Grosser

Marit Synnestvedt

Rolf Kaaresen

Burkhard Brandt

Jahn M Nesland

Klaus Pantel
email: pantel@uke.de.

Christine Zu Eulenburg

Bjorn Naume

Detection and clinical relevance of early disseminated breast cancer cells depend on their cytokeratin expression pattern

Keywords: anti-cytokeratin antibodies, bone marrow, breast cancer, disseminated tumor cells, micrometastasis

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Metastasis is the main cause of cancer-related death and the skeleton is the most prominent site of metastatic relapse in breast cancer. The presence of disseminated tumor cells (DTC) in bone marrow of breast cancer patients serves as a surrogate marker for early micrometastatic spread [1]. Moreover, the recent data on the effect of bisphosphonate treatment on prevention of metastatic relapse in and outside bone [2] supports the assumption that bone marrow might be a reservoir for DTC from where they can disseminate into other organs [3,4]. It can even be speculated that DTC in bone marrow may use the same niches as hematopoietic stem cells. This might explain the observation that DTC can be comobilized with hematopoietic stem cells following induction treatment before high-dose chemotherapy [5]. Moreover, Bidard et al. [6] recently reported a strong correlation between the presence of DTC in bone marrow and local relapse in breast cancer, suggesting that DTC may re-circulate from the bone marrow back to the primary site of tumor growth [3]. This provocative hypothesis is also supported by recent experimental data of Joan Massague´s group obtained in mouse models [7]. Thus, despite the recent focus on the detection of tumor cells circulating in the peripheral blood, screening of bone marrow for DTC might still have substantial future applications with regard to stratification and monitoring of therapies affecting the interaction between metastatic cells and bone marrow environment.

However, the reliability of current DTC detection assays remains still under debate. One main reason for discrepant findings might be the heterogeneity in biological properties of DTC [4] which may affect their detection by specific antibodies or mRNA target transcripts. Most of the DTC detection methods are based on immunocytochemical staining with antibodies directed against cytokeratins (CK) [8][9][10]. Numerous "broad spectrum" CK antibodies recognizing a common epitope on various CK proteins exist. However, the specificities of these antibodies differ considerably and are not well defined. CK constitute the largest intermediate filament protein subgroup and represent a multigene family with more than 20 different types of polypeptides that are divided into acidic type I (CK9-CK20) and basic type II (CK1-CK8) keratins [11]. CK form the cytoskeleton of epithelial cells and their main function is to maintain the epithelial cell integrity. The most commonly used broad spectrum anti-CK antibodies, A45-B/B3 and AE1/AE3 (hereafter referred to as "A45" and "AE"), have been shown to be specific for DTC detection as shown by analysis of large cohorts of noncancer control patients [12][13][14][15]. Although both, A45 and AE1/AE3, are broad spectrum anti-CK monoclonal antibodies, difference in the antibody epitope binding might potentially give different DTC results in individual cases because CK expression varies considerably in breast cancer cells during tumor progression. [16,17] Individual CK proteins (e.g. CK18) can be down-regulated as a consequence of an epithelial-mesenchymal transition [18], an important process recently linked to cancer stem cell behavior [4].

Here we compared the epitope specificity, and in particular the clinical utility of monoclonal anti-CK antibodies A45 and AE for DTC detection in bone marrow of patients with primary breast cancer. Our results suggest that both antibodies recognize separate biological subsets of DTC probably expressing differential patterns of CK proteins, and these cells appear to be relevant in different stages of breast cancer progression. available samples for the purpose of this study). 415 patients were enrolled in this study of which 391 cases were evaluable with both methods. The evaluable cohort consisted of 66 node positive, 324 pN0, and one pNX patient (clinically N0). For the statistical analyses, the pNX patient was included in the node negative group.

Material and Methods

Patients

Bone marrow was aspirated bilaterally from both the anterior and posterior iliac crests (10ml/site) at the time of primary surgery. From all patients, written informed consent was obtained prior to any study-related procedures. The study was approved by the Regional Ethic Committee in Norway. If indicated adjuvant chemotherapy and/or endocrine therapy (tamoxifen) were administered, according to the national guidelines between 1995 and 1998 [15].

Bone marrow specimen

The following procedures were accomplished under sterile conditions. Bone marrow aspirates were diluted 1:1 in PBS (1x phosphate buffered saline, Life Technologies, Inc., Roskilde, Denmark) and separated by density centrifugation using Lymphoprep (Nycomed, Oslo, Norway). Mononuclear cells (MNC) were collected from the interphase layer, and washed twice in PBS with 10% FCS (fetal calf serum; Biological Industries, Kibbutz Beit Haemek, Israel). Direct cytospins were prepared by centrifuging the BM MNC down onto poly-L-lysine coated glass slides (0.5x10 6 MNC/slide) using a Hettich cytocentrifuge (Tutlingen, Germany). The slides were air-dried overnight and stored at -80ºC until immunostaining was performed.

Immunocytochemical staining

In Brief, the A45-B/B3 (AS Diagnostics, Huckeswagen, Germany, www.epimet.de) is a mouse IgG1 monoclonal antibody reactive with a conformational epitope of native cytokeratin heteropolymers [19,20]. The recognition of CK8 as part of the heterotypic complex with CK18 has been shown [20]. The two IgG1 mouse monoclonal antibodies AE1 and AE3 (Sanbio, Uden, The Netherlands, www.sanbio.nl) react with acidic and basic keratins respectively, which should cover a spectrum of CKs, including CK10, CK14-16 and CK19 (AE1) and CK 1-8 (AE3) ([21, 22], and J. Huijbregts, Monosan, Sanbio, Uden, The Netherlands; personal communication). For DTC detection, AE1 and AE3 are mixed in a ratio of 1:1. mouse IgG1 (Sigma Chemical Co.,St. Louis,MO,www.sigmaaldrich.com) or mouse anti-FITC monoclonal antibody (IgG1; Micromet, Munich, Germany, www.micromet.de), lacking any known reactivity for epithelial cells or bone marrow cells, was used as isotype specific negative control antibody. For the A45 and the AE protocols the same MOPC-21/FITC concentrations as for the anti-cytokeratin antibodies were used. As positive control to each staining run, either cytospins of the CK-positive breast cancer cell line MCF-7 mixed with the Chinese hamster fibroblast cell line 3T3 (A45), or normal BM MNC spiked with MCF-7 cells (AE) were used.. Staining of cytospins with AE antibodies has been performed previously, applying the APAAP method for visualization of antibody-bound cells [14,15]. For the purpose of this study, additional slides were stained with A45, followed by the APAAP visualization step. The staining protocols have been described previously [12].

In brief, incubation times for AE and A45 were 30 min and 45 min, respectively.

As secondary and tertiary antibodies, polyclonal rabbit anti-mouse antibodies (Z 259, DAKO, Denmark, www.dako.com), and a mouse monoclonal antibody alkaline phosphatase(AP)-anti-AP (D 651, DAKO, Denmark) were used, respectively. AP-labeled cells were visualized by a red color reaction involving New Fuchsin (Aldrich Chemicals, catalogue no. 229318, www.sigmaaldrich.com), naphtol-AS-biphosphate (Sigma, catalogue no. N-2250) and levamisole (Sigma, catalogue no. L-9756). Finally the slides were counterstained with hematoxylin and mounted in Kaiser's glycerine-gelatin (Chroma Gesellschaft Gmbh, Munster, Germany, www.chroma.de). Further staining details are described in the Online Resource. Previously, the specificity of both protocols was proven by analysis of normal bone marrow control samples from 48 healthy donors [12]. Sensitivity and reproducibility of the A45 and AE protocols have been addressed previously [10,13,14].

The double staining procedure is described in the supplementary Online Resource.

DTC detection

The A45-and AE-stained slides were analyzed by automated screening (10X and 40X magnification) performed by screening systems from Chromavision (ACIS system, San Juan Capistrano, California; used in Hamburg) and Applied Imaging (Ariol system, Applied Imaging, A Genetix Company, New Milton, Great Britain; used in Hamburg and Oslo), respectively. Both systems include an initial, automated screening of the slides, followed by a review procedure during which the investigators (K.E., E.B., and K.P.) morphologically classified the detected elements in a blinded fashion. Detected cells are presented on the screen, but may optionally also be evaluated in the system's microscope using an instant relocation facility. The computerized microscopes have software programs that are optimized for rare cell detection and imaging. The two machines' detection thresholds were adjusted for detection sensitivity at the same level, and comparison between the two systems showed no significant differences. A detailed description of the DTC evaluation is provided in the Online Resource.

Antibody specificity for selected cytokeratins

The experimental procedures of two-dimensional gel electrophoresis, Western Blot and mass spectrometry are described in Bartkowiak et al. [23], see Online Resource.

Study design and Statistics

This study was carried out as a retrospective longitudinal observational study of the 391 breast cancer patients evaluated with both markers. Inclusion criteria and selection of patients are described in the "Patients" section above. Wherever possible, we have adhered to the REMARK criteria for tumor marker studies as published by McShane et al. [24]. Statistical analyses were carried out based on patient records in the Oslo database. The primary end points were distant disease free survival (DDFS) and breast cancer specific survival (BCSS), measured from the date of bone marrow aspiration at primary surgery to the time of the last follow-up visit, systemic relapse (for DDFS) or death (for BCSS). Median followup were 83 months (range 2-115 months) for time to relapse and 99 months (5-118 months) for time to death.

All statistical analyses were conducted with SPSS 15.0 or Stata 9.0, holding a level of significance of 0.05 for every test.

Univariate Analysis

Differences between clinico-pathologic parameters and DTC status, where one DTC per 2 x 10e6 analyzed bone marrow mononuclear cells were recorded as positive status, were analyzed by two-sided Chi2 tests (Pearson) or Exact tests (Fisher) and t-tests. Breast cancer specific survival and distant disease-free survival (DDFS) times were calculated and analyzed by Kaplan-Meier curves.

Statistically significant outcome differences between patients with DTC and without DTC were identified using log-rank tests.

Multivariate Analysis

To investigate independent prognostic factors influencing survival and disease progression, multivariate analysis by the Cox Proportional Hazards Model was applied. Important adjusting covariates of prognostic relevance included in this study were: tumor size and grade, nodal status and hormone receptor status. Since the hormone receptor status fails the assumption of proportional hazards in the analysis of DDFS, it was included as a stratification parameter.

Results

Specificity of the anti-CK antibodies AE and A45 used for DTC detection

To investigate the reactivity and specificity of the CK specific antibodies AE (AE1/AE3) and A45 (A45-B/B3), cell lysate of the basal breast cancer cell line MDA-MB-468 served as a reference protein extract and the cell extract of the luminal breast cancer cell line SKBR3 was used for confirmation. The cell lysates were separated by two-dimensional gel electrophoresis (Online Resource Fig. 1&3). The protein identification by mass spectrometry includes the CK that are significant for detection and classification of breast cancer such as CK5, CK7, CK8, CK17, CK18, and CK19 [25,26] (Online Resource Table 2).

Application of AE to the reference protein extract by 2-DE western blot revealed detection of CK5, CK7, CK8 and CK19, whereas no specific signals were obtained for CK 17 and CK18 (Fig. 1a). Using A45, specific signals for CK7 and CK18 but not for CK5 and CK17 were observed (Fig. 1b); however, weak signals were detected at the coordinates for CK8. Overlay of the X-ray films with the corresponding colloidal Coomassie stained PSQ membranes showed that the signals detected in close proximity to CK19 do not correspond with the CK19 protein spots on the 2-D gels. Therefore, no specific signals were detected by A45 for CK19.

Patient and DTC detection characteristics

Of the samples available for this study, a total of 391 patients had evaluable DTC results for both the A45 and AE protocols. Median patient age was 58 years (range: 27-87). There was no statistical difference in median age between the bone marrow-positive and bone marrow-negative group (t-test, p=0.106; data not shown). The node negative patients had smaller primary tumours (72% pT1, 25% pT2, 1% pT3, 2% unknown) than the node positive patients (49% pT1 tumours, 27% pT2 and 18% pT3 (6% unknown)). Thirty-one percent (122/391) of all patients received adjuvant systemic treatment (21% of node negative, 89% of node positive patients), including endocrine therapy and/or chemotherapy, 27% (100/391) received hormonal therapy, and 10% (38/391) were under a combined regimen of chemotherapy plus tamoxifen (data not shown).

The A45 and the AE staining from the 66 node positive cases were scored by both participating institutions and the two independent scorings ("Oslo" and "Hamburg") were compared. The rates of positivity for AE and for A45 were correspondent: By both scorings 12.1% (8/66) of the patients had DTC detected by A45 and 19.7% (13/66) by AE (Online Resource Table 1). Inter-observer comparisons did not show identical results, but highly significant correlations between Oslo and Hamburg scorings for both staining protocols; a 93.9% (p<0.001) and 97.0% (p<0.001) congruence in results for A45 and AE, respectively. The results support that an overall comparison of the A45 and AE staining results could be achieved by using one scoring only which here is the Oslo scoring.

Analysing all the patient samples, numbers of detected DTC ranged from 1 to 5 per 2x10 6 mononuclear cells (MNC) analyzed and were not statistically different between the two antibodies. Considering all the included cases, 6.1% (24/391) had A45-positive DTC in bone marrow and 10.5% (41/391) had AE-positive DTC (Table 1). Overall, 16.1% (63/391) of the patients had DTC in the bone marrow (AE and A45 in combination). Congruence in results between the two antibodies was high (84.4%), but the concordance was only 3.2% (2/63) within DTC-positive bone marrows (Table 1). No statistical correlation between A45 and AE was found (p=1.000). For the subgroup of node negative patients, 4.9% (16/325) of the bone marrows were positive for A45 and 8.6% (28/325) for AE (Table 2), and there was no overlap between the positive cases. By combined analysis of AE and A45, 13.5% (44/325) were DTC-positive (data not shown). Within the node positive subgroup, 12.1% (8/66) patients had DTC detected by A45, and 19.7% (13/66) by AE. Two patients had overlapping DTC results by A45 and AE.

Numbers of detected DTC ranged from 1 to 4 per 2x10 6 MNC in the node negative, and from 1 to 5 cells per 2x10 6 MNC in the node positive subgroup.

Tumor cell numbers were not statistically different for A45 and AE.

The different CK patterns recognized by the antibodies and the small overlap of AE-positive and A45-positive cases directed us to the question whether AE and A45 detect different subpopulations of DTC in vivo. Immunocytochemical double staining (i.e., AE and A45 were applied to the same slide) revealed subsets of DTC labeled with both antibodies but also DTC exclusively stained with either A45 or AE (Fig. 3).

Histopathological correlations

The occurrence of DTC was correlated to primary tumor characteristics. A significant association between the antibodies and the nodal status was observed for AE (p=0.019), for A45 (p=0.036; Table 2) and for both antibodies combined (p=0.003; data not shown). An increased number of DTC-positive bone marrows were detected by AE in hormone receptor (HR)-negative versus HR-positive cases (p=0.006). In contrast, all but one patients with DTC detected by A45 (23/24) were HR-positive (p=0.061). Higher DTC detection rates with increasing T-status were indicated for AE (p=0.056) and for both antibodies combined (p=0.016; data not shown; for A45, p=0.365). Other parameters were not significantly different between DTC-positive and DTC-negative patients for either staining protocol (Table 2).

Survival analysis

During the observation period, 67/391 patients (17.1%) died, of those 43 patients of breast cancer. There were 57/391 patients (14.6%) who suffered from systemic relapse during follow-up. In total, 24.6% of patients who relapsed had DTC in their bone marrow detected by either AE and/or A45, whereas only 14.8% of the relapse-free patients harbored DTC (p=0.065; Fisher's exact test). DTC detected by A45 alone were found significantly more frequent in patients who suffered from relapse than in relapse-free patients (p=0.039; Table 2).

The Kaplan Meier survival plots for the entire cohort of 391 patients, according to the A45 and AE staining, are presented in Fig. 2a. In contrast to AE (p=0.487), univariate analysis (log-rank test) revealed that DDFS was associated with the presence of A45-detected DTC as compared with their absence (p=0.023). BCSS did not significantly correlate to DTC status.

Within the node positive cohort (Fig. 2b), the presence of DTC detected by AE alone (p=0.036) or by the combination of A45 and/or AE (p=0.044) was correlated to reduced BCSS. This was not observed for A45 alone (p=0.151).

Within the subgroup of node negative patients, no significant association between presence of DTC and survival was observed (Fig. 2c). For A45-positive patients an insignificant trend towards higher risk of early systemic recurrence compared to A45-negative patients was indicated (p=0.108; Fig. 2c).

Multivariate analysis

Multivariate Cox regression analysis (n=355) included DTC status by A45 and by AE, adjusting for tumor size, nodal status, hormone receptor status and tumor grade. Presence of DTC detected by A45 was an independent significant prognostic factor for DDFS (HR 2.2;95%CI:[1.05 ;4,53]; p=0.036; Table 3).

Tumor grade was a strong prognostic factor for both BCSS and DDFS, whereas tumor size was related to DDFS and nodal status to BCSS. The Cox proportional hazards regression analysis for DDFS had to be stratified by the hormone receptor status because the model requirements are not met. In that case, it is not possible to estimate a constant hazard ratio for hormone receptor status. The results were not significantly altered when treatment status was included in the analyses.

Taken into account the type of systemic therapy administered (tamoxifen only, chemotherapy and tamoxifen, chemotherapy alone), no interactions between the results obtained with A45 or AE and either therapy regimen were revealed (data not shown).

Discussion

This study describes, for the first time, the parallel assessment of the two pan anti-CK antibodies most frequently used for DTC detection. Our results revealed that these antibodies appear to identify different populations of DTC, depending on the primary tumor biology and disease stage, with important implications for their clinical utility.

The DTC detection rate in the present study was low. Each antibody by itself resulted in 6.2% (A45) and 10.5% (AE) positivity. Main reason for the low positivity rates may be the very favorable clinical characteristics of the investigated patient cohort with more than 80% pN0 cases and over 68% T1 tumors. This consideration is supported by the finding that the detection rates within the node positive subgroup were higher for both antibodies, with 12.1% for A45 and 19.7% for AE. However, other explanations for the low overall detection rate and the difference in A45 and AE1 staining results may potentially include other (yet unknown) methodological issues as well as Poisson distribution of rare events, which may affect the reproducibility of the results independent of the antibody applied. In our study, as well as in other reports with a fairly low DTC detection rate, a standardized and careful cell evaluation was performed, which excludes occasional ICC positive cells with hematopoietic cell-compatible cell morphology as DTC. Such stained cells with hematopoetic cell characteristics have been shown to lack prognostic significance [27]. Other groups reported higher incidences of DTC in bone marrow but with less stringent criteria for DTC positivity [28][29][30].

The Oslo group has previously reported lower DTC prevalence than the We found that only a small percentage of all positive cases were detected by A45 and AE in parallel. The most striking difference seems to appear between the hormone receptor positive and negative patients. Histopathological correlation shows that A45 primarily detected DTC in HR-positive patients, while AE detected DTC in relatively high frequency in HR-negative patients. This observation can be explained by a different CK expression pattern in HR-positive and HR-negative primary tumors, with up-regulation of CK8, 18 and 19 in HRpositive tumors and down-regulation of CK5-7 and CK14-17, as compared to HRnegative [31]. As indicated by our present proteomics analysis, A45 primarily detected CK7 and CK18, which could explain the more selective detection of DTC in patients with HR-positive tumors. In contrast, in addition to CK8 and CK19, AE detected CK5 and 7 -the latter two mainly detected in tumor cells of HR-negative patients.

To identify the anti-CK antibody specificities, we have applied an extremely reliable and highly accurate proteomic approach [23]. The well characterized cell extract of the basal breast cancer cell line, MDA-MB-468, served as a reference protein mixture and the cell extract of the luminal breast cancer cell line, SKBR3, was used for confirmation. These cell lines express all of the common CK proteins known to play a role in breast cancer and therefore provide a sufficient basis to profile the reaction pattern of the anti-CK antibodies used in our study.

Most importantly, the present study shows differences in the prognostic information obtained if AE and A45 are applied for DTC detection. Analysis of our 391 patients (83% node negative and 17% node positive) confirms that the presence of A45-detected DTC in bone marrow predicts systemic relapse, and is an independent prognostic factor (Cox multivariate analysis). A trend for reduced DDFS by A45 was also observed for the node negative subgroup (Fig. 2b, p=0.108). This was not the case for AE. However, for the node positive subgroup, the opposite result was obtained, AE-based DTC status (Fig. 2a,p=0.036) correlated to survival whereas A45 did not. The difference between the node negative and node positive cohort also explains why the combined results of AE and A45 did not result in increased prognostic information. These results indicate that the CK expression pattern in DTC (and hence the difference in A45 and AE staining) may vary during the natural course of the disease; an assumption supported by previous reports on down-regulation of CK proteins during breast cancer progression [16,17]. Our A45-AE-double staining experiment furthermore supports the assumption that CK expression is heterogeneous in DTC. Korsching et al. reported [32,33] that up-regulation of CK5 (detected by AE only and missed by A45) goes along with a progenitor cell and therefore more aggressive DTC phenotype and disease progression. This might explain why DTC detected by AE acquired prognostic significance in the subgroup of node positive, i.e. more advanced patients. However, it is conceivable that CK5-expressing DTC might also be present in lymph node negative patients but maybe at a lower frequency, which could be one explanation for the different prognostic information between the nodal subgroups. Furthermore, as these analyses are retrospective, additional studies would be needed before drawing definite conclusions.

This study has implications for future studies using DTC analysis for risk assessment and therapy monitoring in breast cancer patients, and the implications are also applicable to the detection of circulating tumor cells in the peripheral blood of cancer patients [3]. The findings underlie the unmet need for a detailed knowledge of the staining patterns for "broad spectrum" CK antibodies. This knowledge is important for both interpretation of the results of previously published DTC studies and selection of the most optimal antibody or combination of antibodies to be used in future DTC studies. Information of differences in expression patterns of the DTC marker genes within subgroups of breast cancer

[34] will be important for further optimization of DTC detection. This will be of particular importance in the context of EMT and cancer stem cell properties [4,35] and might affect future strategies for the detection of disseminating tumor cells in the bone marrow and peripheral blood.

Tables

  Women with early breast cancer were treated at five hospitals in the Oslo region between 1995 and 1998. The patients within this study are all included in the Oslo micrometastasis study, including 817 patients with known DTC status at time of operation, evaluated by AE immunocytochemical (ICC) staining. The selection of patients were based on available additional samples to perform additional analyses with the following selection criteria: 1) Node negative patients, as AE-based detection for DTC in this group has previously been shown not to be associated with future metastasis and death (except for theT1pN0 non-adjuvant treated subgroup [15]. 2) A selection of node positive patients with a frequency of DTCpositive cases in line with what reported in the original study (approximately 20%, but not included samples with ≥3 DTC by AE staining, because of no

  Hamburg group[13][14][15]. However, comparing the DTC scorings by the two centers in the present study, only minor differences were revealed. The satisfactory correlation supported the use of one scoring for the comparison of AE-and A45-based DTC detection and correlation to clinical outcome. Both antibodies are well-established and have been recommended for DTC detection in bone marrow in a consensus paper by German, Austrian and Swiss societies of senology [9].

FiguresFig. 1

 1 Figures

Fig. 2

 2 Fig. 2 Kaplan-Meier curve for DDFS (upper row) and BCSS (bottom row) related to DTC status (a) in all patients (n=391), (b) in node-positive patients (n=66), and (c) in node-negative patients (n=325), for A45 (left), for AE (center), and for A45 and AE combined analysis (right). Green lines indicate DTC-positive cases, blue lines DTC-negative cases.

Fig. 3

 3 Fig. 3Bone marrow sample of a breast cancer patient double-stained with AE coupled to Alexa 488 (green) and A45 directly conjugated with Cy3 (red). Images were taken with the Ariol™ system (Applied Imaging, A Genetix Company, New Milton, Great Britain).

Table 1

 1 Cross table of disseminated tumor cell status in breast cancer patients (n=391) as defined by staining with AE and A45 antibodies.

		AE negative	AE positive	Total
	A45 negative	328 83.9%	39 10.0%	367 93.9%
	A45 positive	22 5.6%	2 0.5%	24 6.1%
	Total	350 89.5%	41 10.5%	391 100.0%

Table 2

 2 Prevalence of disseminated tumor cells in bone marrow according to histopathological parameters and recurrence status.

	Number of	Number of
	A45-B/B	AE1/AE3
	positive (%)	positive (%)

a HR Status, hormone receptor status includes estrogen and/or progesterone receptors; b Statistical significance; c Borderline significance.

Table 3

 3 Multivariate Cox regression analysis for DDFS and BCSS including relevant clinical variables. P, p-value; HR, Hazard ratio; CI, Confidence interval; DDFS, Relapse free survival (n=351); BCSS, Breast cancer specific survival (n=355). n.i., Hormone Receptor status not included; the hazard ratios for the other variables in the stratified Cox-Model are estimated adjusted for hormone receptor status. Because the covariate 'Hormone Receptor' does not meet the requirement of proportional hazards, a multivariate Cox regression stratified by this factor was performed.

	Characteristic			DDFS			BCSS
		P		HR	CI	P	HR	CI
	Tumor Size (pT1vspT2/3)	0.045	1.7	1.01-2.68	0.085	1.8	0.92-3.43
	Nodal Status (pN0vspN1-3)	0.062	1.7	0.97-3.02	<0.001	3.6	1.81-7.22
	Tumor Grade (G1/2vsG3)	<0.001	0.2	0.07-0.43	0.003	0.1	0.02-0.46
	Tumor Grade (G1vsG2/3)	0.005	0.5	0.25-0.79	0.001	0.3	0.13-0.59
	Receptor (pos/neg)	n.i.	a	n.i.	n.i.	0.243	0.6	0.31-1.35
	DTC (A45)	0.036	2.2	1.05-4.53	0.971	1.0	0.30-3.49
	DTC (AE)	0.493	0.7	0.31-1.75	0.981	1.0	0.38-2.60

a

Acknowledgements

We thank Sonja Santjer, Cornelia Coith, Antje Andreas and Sandra Schwentesius for their excellent technical assistance. The study was funded by the DISMAL project by the European Commission (contract no. LSHC-CT-2005-018911), Norwegian Cancer Society and Margaret Solbergs Legacy.


Alain Giorgetti
email: giorgett@lifc.univ-fcomte.fr

Julien Groslambert
email: julien.groslambert@trusted-labs.com

Jacques Julliand
email: julliand@lifc.univ-fcomte.fr

Olga Kouchnarenko

Verification of class liveness properties with Java modeling language

come   L'archive ouverte pluridisciplinaire

Introduction

Component-based development provides signicant advantages portability, adaptability, re-usability, etc. when developing, e.g., Java Card smart card applications [START_REF] Breunesse | Formal methods for smart cards: an experience report[END_REF] or when composing Web services within Service Component Architecture (SCA) a relatively new initiative advocated by users of Java technology.

In this framework, the use of components of distributed applications or component-based applications ad'hoc semantics of a Java class). Next, Section 5 denes the liveness clause and its formal semantics. Section 5 also presents the verication of liveness properties on a class in isolation through appropriate annotation generation. Section 6 presents the application of the annotation generation method to the JTPL temporal liveness properties based on their translation into the liveness clause that we propose to extend JML. Section 7 presents the JAG tool implementing this automatic generation of annotations.

Section 8 concludes by giving some perspectives and future work.

2 Overview of JML and Example JML (Java Modeling Language) [START_REF] Leavens | JML Reference Manual[END_REF] is a specication language especially tailored for Java applications.

Originally, JML was proposed by G.T. Leavens and his team; the development of JML is now a community eort. JML has been successfully used in several case studies to specify Java applications, and more especially to specify smart card applications [START_REF] Breunesse | Formal methods for smart cards: an experience report[END_REF][START_REF] Jacobs | Formal Verication of a Commercial Smart Card Applet with Multiple Tools[END_REF]. JML is developed following the Design by Contract approach [START_REF] Meyer | Object-Oriented Software Construction[END_REF], where classes are annotated with class invariants and method pre-and post-conditions. The predicates are side-eect free boolean Java expressions, extended with specic constructs. Specications are written as Java comments marked with an @, i.e., annotations follow //@ or are enclosed between /*@ and @*/. Figure 1 presents some JML annotations on the simple example of a buer.

The class Buffer works as follows: a method storeData() customises the application by setting the transaction length. Then, one can initialise a new transaction with the method begin(), creating a new temporary buffer. Afterwards, a write() method lls the modications in the temporary buffer that is validated, i.e., assigned to the attribute status, by an invocation of commit(). It is also possible to abort the transaction by an invocation of the method abort().

Figure 1 displays a class invariant, i.e. a predicate that has to hold on every so-called JML visible state. History constraints allow expressing a relation between the pre-and post-state of all methods.

Pre-state values of expressions are denoted by the JML keyword \old. Using the clause for, one may specify the methods list for which the history constraint must be satised. When this clause is omitted, the constraint must hold for all the class methods. The clause requires denotes the pre-condition of the method, i.e., a predicate that must be true when the method is called. A post-condition is expressed with an ensures clause. A method may exceptionally terminate by throwing an exception and satisfying the exceptional post-condition (signals clause). The method specication can also contain a diverges clause (not displayed in this example). If the predicate of a diverges clause of a method m is satised by the pre-state of m, then the execution of m may not terminate. Otherwise the method must terminate. By default, the JML diverges clause is set to false. JML also introduces its own variables declared with the keyword ghost. A special set annotation exists to assign their value. For instance, trDepth = true means that a transaction is in progress. This variable allows expressing that every opened transaction must eventually be closed. This is an example of liveness property that will be translated into a set of JML annotations. The correctness of a Java class w.r.t. JML annotations can be established by modelchecking [START_REF] Robby | Checking Strong Specications Using an Extensible Software Model Checking Framework[END_REF] or by a prover (B or Coq) via a proof obligation generator (Jack [START_REF] Burdy | Java Applet Correctness: a Developer-Oriented Approach[END_REF] or Krakatoa [START_REF] Marché | The Krakatoa tool for certication of Java/Java Card programs annotated in JML[END_REF]).

Preliminaries

This section introduces some denitions and notations used in the other sections. It recalls the notion of sequence and some useful results for the existence of xpoints in lattices.

Notations

Familiarity with basic set theory is assumed. Given a binary relation R

⊆ S 1 × S 2 , dom(R) is its domain, ran(R) is its range and R -1 is the inverse relation. If dom(R) = S 1 then the relation is total. A relation f ⊆ S 1 ×S 2 is a partial function from S 1 to S
f [x → y](u) =      f (u) if u = x y if u = x More generally, we write f [x 1 → y 1 , . . . , x n → y n ], instead of f [x 1 → y 1 ] . . . [x n → y n ], when the x 1 . . . x n are all dierent.

Sequences

Let S be a (nonempty) set. A sequence is a partial function σ from N to S such that the set dom(σ) is either N or a nite subset [0, ..., k] for some k in N. The concatenation α.β of two sequences α, β ∈ S * ω of length l = len(α) and m = len(β) is a sequence of length len(α.β) = l ⊕ m, where ⊕ extends the addition of N to N ∪ {ω}, with ω ⊕ n = n ⊕ ω = ω for any n ∈ N ∪ {ω}. σ = α.β is dened by σ(i) = α(i) for 0 ≤ i < l and σ(i) = β(i -l) for l ≤ i < len(σ).

Concatenation of sequences extends to sets of sequences in a standard way, with the same notation.

Two nonempty sequences α, β ∈ S +ω of length l = len(α) and m = len(β) are joinable i last(α) is β(0)

or ω. When they are joinable, their join (or junction) α β is a sequence σ of length len(σ

) = (l ⊕ m) 1,
where extends the subtraction of N to N ∪ {ω}, with ω n = ω for any n ∈ N ∪ {ω}. σ = α β is such that σ(i) = α(i) for all 0 ≤ i < l and σ(i) = β(i -l + 1) for all l ≤ i < len(σ) when l < ω. The junction S T of the sets of nonempty sequences S and T is the set of junctions α β of joinable sequences α ∈ S and β ∈ T.

Complete Lattices

A partial order on a set S is a relation on S which is reexive (∀x ∈ S. x x), transitive (∀x, y, z ∈ S. (x y ∧ y z) ⇒ x z) and antisymmetric (∀x, y ∈ S. (x y ∧ y x) ⇒ x = y). A partially ordered set S, , or poset, is a set equipped with a partial order . A lower bound l of U ⊆ S is an element l of S such that ∀x ∈ U. l x. A greatest lower bound of U is a lower bound g of U such that l g holds for all lower bound l of U. A (least) upper bound of U for is a (greatest) lower bound of U for the inverse partial order -1 . By antisymmetry of , greatest lower and least upper bounds, when they exist, are unique.

A complete lattice S, , , is a poset S, where every subset U ⊆ S has a least upper bound, denoted U, and a greatest lower bound, denoted U. An endofunction f of S is monotone if ∀x, y ∈ S. x y ⇒ f (x) f (y). A consequence of Tarski's xpoint theorem [START_REF] Tarski | A lattice-theoretical xpoint theorem and its applications[END_REF] is the existence of least and greatest xpoints for any monotone function in a complete lattice.

Proposition 1 Every monotone endofunction f on a complete lattice L, , , admits a least xpoint

lfp(f) = def {x|x ∈ L ∧ f (x) x} and a greatest xpoint gfp(f) = def {x|x ∈ L ∧ x f (x)}.

Sequence Set Lattice

When a program can either run forever or end, its execution (or trace) semantics is a set of nite or innite sequences (of states). Following [START_REF] Cousot | Constructive design of a hierarchy of semantics of a transition system by abstract interpretation[END_REF], these sets can be specied as xpoints in the set 2 S +ω of sets of nonempty nite or innite sequences. The following proposition denes a lattice over this set by fusion of the complete lattices 2 S + , ⊆, ∪, ∩ and 2 S ω , ⊇, ∩, ∪ of sets of respectively nonempty nite and innite sequences. A proof that they are complete lattices can be found in [START_REF] Cousot | Constructive design of a hierarchy of semantics of a transition system by abstract interpretation[END_REF], Th. 11 and 12. In all that follows, X + (resp. X ω ) shortens X ∩ S + (resp. X ∩ S ω ) for any X in 2 S +ω .

Proposition 2 (Corollary of [START_REF] Cousot | Constructive design of a hierarchy of semantics of a transition system by abstract interpretation[END_REF], Th. 9) Let 2 S +ω be the (disjoint) union of 2 S + and 2 S ω . For any

X in 2 S +ω , let be dened by X Y = X + ⊆ Y + ∧ X ω ⊇ Y ω .
For any subset Z of 2 S +ω , let and be respectively dened by

Z = X∈Z X + ∪ X∈Z X ω and Z = X∈Z X + ∪ X∈Z X ω .
Then 2 S +ω , , , is a complete lattice.

Execution Semantics

Our aim is to verify liveness properties of Java/JML components. A suitable semantics for this is a set of maximal execution paths. Intuitively, an execution path (or simply an execution) is a sequence of states reached during an execution of the class. An execution path is maximal if it cannot be extended to form a longer execution path. A maximal execution path is either innite or is terminating with a blocking state.

Context Restrictions

We study a component that is a Java class enriched with some JML annotations: invariant, constraint and ghost variables for the class, behavior for methods and set in their bodies. The annotation pure means that a method is side-eect free. The annotations helper and assignable are useless in dening the liveness properties that we address. Consequently, we do not take these annotations into account.

We do not address the problems of inheritance, multithreading and exception hierarchy. To simplify the presentation, we do not take into account the nalizers and the static methods. The execution of the component environment is restricted to creating only one instance of the class. The execution invokes only the non static methods.

We assume that the environment and the class respect the contract dened by the JML specications.

That means that the environment calls method m from a memory state that satises its requires By a desugaring operation [START_REF] Raghavan | Desugaring JML method specications[END_REF], the method m behaviours can be reduced to a single canonical be- The addressed Java subset to dene method bodies body m is composed of atomic and method call statements respectively denoted by as and m(E, . . . , E), sequential, conditional and iterative statement compositions, and exception handling. An atomic statement is any statement that does not dene other memory states than the states before and after its execution. A typical example is an assignment of a variable in V C .

Denition 2 (Java Subset) Let E be a Java expression, m a Java identier and P a Java predicate (a boolean Java expression). We consider the Java statement subset T dened by the following abstract syntax:

T ::= as | m(E, . . . , E) | T ; T | if (P ) {T } else {T } | while (P ){T } | throw | try {T } catch {T } | try {T } finally {T } .
A memory state assigns values to variables. For a component in isolation, we consider three sets of variables, namely: the set V C of attributes and ghost variables, the set P C = m∈MC paramList m of parameters of all the methods (to simplify, we assume that distinct methods have disjoint parameter sets), and a set of three special variables to control the execution.

Denition 3 (Memory State) A memory state s is composed of:

• two total functions V C → VAL and P C → VAL ∪ {⊥}, where VAL is the set of all values of the dierent Java types and ⊥ ∈ VAL; the former function assigns a value to any attribute and ghost variable of C ; the latter assigns a value to any parameter of any method of C ; when the parameter is not used, its value is undened -denoted ⊥.

• a boolean variable excp; the predicate s(excp) indicates that an exception has been thrown,

• a variable cM ∈ M C , indicating the name of the method currently performed,

• a variable sH, that is a natural number that represents the height of the execution stack.

This denition simplies memory models for object oriented languages [START_REF] Marché | The Krakatoa tool for certication of Java/Java Card programs annotated in JML[END_REF][START_REF] Van Den Berg | A Type-Theoretic Memory Model for Verication of Sequential Java Programs[END_REF]. The Java memory also contains an execution stack [START_REF] Lindholm | The Java Virtual Machine Specication[END_REF]. As in [START_REF] Logozzo | Class Invariants as Abstract Interpretation of Trace Semantics[END_REF], we do not explicitly use the execution stack, but we observe it with the three special variables excp, cM and sH. Given a state s and a variable x in V C ∪ P C ∪ {excp, cM, sH}, s(x) denotes the value of x in the state s, when it is dened. We denote by STATE the set of memory states of a class C .

Let E be a Java/JML expression. We consider an evaluation function, written eval(E, s), that returns the value of E in the state s. Denition 4 (Java Subset Semantics) Let T be a Java statement and s ∈ STATE a memory state without exception (¬s(excp)). The execution s T is dened in Fig. 2, where f as : STATE → STATE is the state transformer of the atomic statement as.

Each equality in this denition must be understood as follows:

1. The execution for an atomic statement as is the output state resulting from as.

2. The rst state s in is a pre-state that contains the value of every parameter of m. In this state, the current method is m and the stack height is incremented. If s in does not satisfy the precondition P m of method m, the execution the execution raises an exception. Otherwise, the state s in is followed by the sequence of states resulting from the execution of the body of m. When this execution is nite, it ends with a last state s exit whose parameters, cM and sH, are equal to their values in the rst state s and whose other values are those of the last state of the body execution.

3. The execution for a sequence of T 1 and T 2 is the concatenation of the executions of T 1 and T 2 if T 1 terminates without raising an exception. Otherwise, it is the execution of T 1 .

4. The execution for the conditional statement is the execution of T 1 if s satises P and the execution of T 2 otherwise.

5. Dening the execution semantics of the iterative while statement is a dicult point. For any predicate P and statement T it is expected that this execution is empty if s does not satisfy P , is the execution of T if T does not terminate or raises an exception, and is otherwise the concatenation of a rst execution of T and the execution of the same iterative statement from the last state of this rst execution of T . To simplify our semantics we dene never an empty execution in such a way the function last is always dened. The semantics of while (false){T } is dened by s. This stuttering has no eect on the visibles states. Last, note that this is an expression of the syntactic statement skip. This is the intended meaning of the fth equality in Fig.

W = (λX.{σ ∈ STATE +ω | len(σ) = 1 ∧ σ(0) |= P } ∪ {σ ∈ STATE +ω | σ ∈ T ∧ σ(0) |= P ∧ last(σ)(excp)} ∪ {σ ∈ STATE +ω | σ ∈ T ∧ σ(0) |= P ∧ ¬last(σ)(excp)} X)
with the convention that ω(excp) = false. On the one hand, this function is monotone. On the other hand, a proof by induction on the statement language shows that the execution set W (X) contains exactly one execution starting from any given state, for any execution set X. Then s while(P ){T } is dened as the execution starting with s in the least xpoint of W .

6. The execution for the try{T 1 }catch{T 2 } statement is the execution of T 1 if T 1 either does not terminate or terminates without raising an exception. Otherwise, when T 1 terminates, the raised exception is removed and the execution continues with the execution of T 2 .

7. The execution for the try{T 1 }finally{T 2 } statement is the execution of T 1 if T 1 does not terminate.

Otherwise, when T 1 terminates either normally or by throwing an exception, the raised exception is caught if necessary and the execution continues with the execution of T 2 .

8. The throw statement assigns the special variable excp to true. If the throw statement is in the T 1 part of a try{T 1 }catch{T 2 } statement, the execution continues with the execution of T 2 as it is specied by its semantics. Otherwise, the execution stops.

Class Semantics

As explained in Sect. 1, we aim to verify that a class C satises a liveness property. This satisfaction obviously depends on the context of use of that class. Here, we focus on the life cycle of a single object of type C , after its construction. We assume the encapsulation hypothesis, i.e. that the class attributes can be modied only by the invocation of class methods. Consequently, the class use only depends upon the manner invoking the class methods. The class executions result from the activation of the constructor followed by a nite or innite sequence of method calls that respect the contract -each of them protected by an exception recuperation statement. This class semantics Σ +ω C is dened in this section.

A method execution at toplevel is a (maximal) execution of a method m that starts from any state where the execution stack is empty and the exception ag is down. The set of executions of a class C at toplevel is denoted C and dened by

C = def { s.s try{m(v(p 1 ), . . . , v(p n ))}catch {} | m ∈ M C ∧ v ∈ paramList m → VAL ∧ s ∈ STATE ∧ ¬s(excp) ∧ s(sH) = 0 ∧ s |= P m }
where paramList m = {p 1 , . . . , p n }.

Let C be an annotated class, STATE its set of states, C ∈ STATE +ω its execution semantics and S 0 ⊆ STATE the set of initial states resulting from the constructor i C of C . The set f (C ) of blocking (or nal) states for the class C is dened by f (C ) = STATE \ {σ(0) | σ ∈ C }. With these notations, the maximal execution semantics of an annotated class can be dened thanks to the following endofunction.

Proposition 3 In the complete lattice 2 STATE +ω , , , , the endofunction F dened by

F (X) = f (C ) ∪ ( C X) is monotone.
Proof Notations are the same as in Prop. 2, except for S replaced here with the set STATE of memory states. By separating nite and innite sequences, one has F (X)

+ = f (C ) ∪ ( C + X + ) and F (X) ω = ( C + X ω ) ∪ C ω . X Y implies that F (X) + ⊆ F (Y ) + and F (X) ω ⊇ F (Y ) ω , i.e. F (X) F (Y ). 2
When C is a transition relation, i.e. when it is a set of executions of length 2, this proposition is a corollary of Th. 13 from [START_REF] Cousot | Constructive design of a hierarchy of semantics of a transition system by abstract interpretation[END_REF], proved by fusion of xpoints on the two lattices of nonempty nite and innite executions. The present result is more general, since C may contain nite executions of any length, and even innite executions. A consequence is that a proof by fusion is no more possible. By Prop. 1 and 3, F admits a leastxpoint, denoted lfp(F ).

Denition 5 (Class Semantics) The restriction of lfp(F ) to executions starting from the states resulting from the constructor is called the class semantics and is denoted Σ +ω C = def lfp(F ) ∩ (S 0 STATE +ω ).

Visible States

The semantics of the JML invariant and constraint clauses is based on the notion of visible states.

This section formalises this notion and its semantics. Under the hypotheses of Sect. 4.1, the original denition of visible states, given in the JML reference manual [START_REF] Leavens | JML Reference Manual[END_REF], is restricted to three cases, as follows.

A visible state is a state that occurs at one of these moments in a program's execution: at the rst state of the execution, just after the end of a constructor invocation that has created the executed object; at the beginning or end of a (non-static non-nalizer) method invocation; outside of the execution of any constructor, nalizer, or method when the execution stack is empty.

Let us rst formalise the notions of pre-and post-states for a method m as follows.

Denition 6 (Pre-and Post-States) Let C be a class, σ ∈ Σ +ω C an execution, m a method of class C and 0 ≤ i < len(σ). For i > 0, the i th state σ(i) of σ is a pre-state of m, denoted prestate(σ, i, m), if σ(i)(cM) = m and σ(i)(sH) = σ(i -1)(sH) + 1. The i th state of σ is a post-state of m, denoted poststate(σ, i, m), if σ(i)(cM) = m and σ(i)(sH) = σ(i + 1)(sH) + 1.

With this denition, for any execution of class C , we formalise in conformity with [START_REF] Leavens | JML Reference Manual[END_REF] what a visible state is. Denition 7 (Visible States) Given an execution σ ∈ Σ +ω C , the i th state σ(i) of σ is a visible state, denoted visible(σ, i), i i = 0, σ(i)(sH) = 0 or there is a method m ∈ M C in C s.t. prestate(σ, i, m) or poststate(σ, i, m).

It is now possible to abstract any execution by keeping only its visible states. The following denition of this abstraction is based on an auxiliary partial function nv : N × Σ +ω C → N, such that nv(i, σ) is the position of the i + 1-th visible state in σ, when it exists. Let min(S) denote the minimum of any subset S of N. nv is inductively dened by nv(0, σ) = min({j | 0 ≤ j < len(σ) ∧ visible(σ, j)}) and nv(i, σ) = min({j | nv(i -1, σ) < j < len(σ) ∧ visible(σ, j)}) for i > 0.

Denition 8 (Visible State Abstraction) The visible state abstraction of a class C , denoted vsa C , is the endofunction of Σ +ω C dened by vsa C (σ)(i) = σ(nv(i, σ)) for any σ in Σ +ω C and any 0 ≤ i < len(σ).

Class in Isolation Semantics

The semantics of a class in isolation is dened as the set of abstractions to visible states of complete (maximal) class executions. Following [START_REF] Logozzo | Class Invariants as Abstract Interpretation of Trace Semantics[END_REF], this execution semantics is called the class in isolation semantics.

It is dened as follows:

Denition 9 (Class In Isolation Semantics) The class in isolation semantics of a class C is dened by

Σ C = def {vsa C (σ) | σ ∈ Σ +ω C }.

Annotated Class Consistency

To express temporal properties by JML annotations, we need an execution semantics of JML annotations.

To our knowledge, JML semantics has been given in terms of wp-calculus (see for example [START_REF] Marché | The Krakatoa tool for certication of Java/Java Card programs annotated in JML[END_REF]), but never in terms of properties of the executions. In this section, we give an execution semantics of JML annotations dening their consistency with the set of executions Σ C of the class in isolation.

In an annotated class, there are three canonical kinds of annotations: invariant, constraint and behavior. Their semantics are given by Def. 11 w.r.t. the denition in [START_REF] Leavens | JML Reference Manual[END_REF]. In Def.

(σ, j, m) ∧ σ(j)(sH) = σ(i)(sH) ∧ ∀k.(i < k < j ⇒ σ(k)(sH) ≥ σ(i)(sH)).
Denition 11 (Consistency) Let C be an annotated class. We dene that an execution σ of Σ C satises a JML annotation A of the class C , denoted σ : A, according to the formulae in Fig. 3.

This denition must be understood as follows:

• Invariant: The invariant must be satised by each visible state (see [START_REF] Bellegarde | Verication of liveness properties with JML[END_REF] in Fig. 3).

• Constraint: For the body of each method included in the for clause, the constraint must hold between two consecutive visible states that arise during the execution of the method, i.e., all visible states between the pre-state and the matching post-state of the method (see [START_REF] Bouquet | Checking JML specications with B machines[END_REF] in Fig. 3).

• Behavior method specication: This JML specication is interpreted over an execution as follows.

If If D m holds and the method terminates, then the pre-state and its matching post-state satisfy the same condition postcontract(σ, j, m, i) as in the previous case (see the case D m in (3)).

Liveness Properties

Liveness properties extend the notion of program termination by stipulating that a program must eventually reach some given states. This section deals with the expression and verication of liveness properties on a class C .

Liveness Operator

The liveness properties under consideration are those expressible by the Loop operator dened in this section. For any state predicate Q, the temporal formula Loop(Q) corresponds to the linear-time temporal logic (LTL) property GF¬Q for innite sequences of states. It is also satised by nite sequences of states ending in a state where Q does not hold. Its semantics is based on the notion of visible states in JML.

It is dened on nite and innite executions as follows:

Denition 12 (Loop Operator) Let Q be a predicate. The execution σ ∈ Σ C satises the liveness

operator Loop(Q), written σ |= Loop(Q), if ∀i. (0 ≤ i < len(σ) ⇒ ∃j. (i ≤ j < len(σ) ∧ σ(j) |= ¬Q)).
This satisfaction relation is lifted up to sets of executions with the semantics that every execution in the set satises the formula.

Class Liveness

In object-oriented programming, dening and checking the satisfaction of a liveness property on a whole program -composed of many classes -may be an heavy task. As a rst step, this section presents the semantics of a liveness property attached to a single Java class.

A

Proving Liveness

Along the line of Floyd's total correctness proof method, we plan to prove liveness with the help of a variant function that assigns a value to each program state. That value should decrease at each program step, according to a well-founded ordering. In the deterministic case, it is sucient [START_REF] Dijkstra | On weak and strong termination[END_REF] to consider variants taking their values in N, totally ordered with <.

In the present case, some program steps are calls to methods of a class C . It is obvious that a call to a side-eect free method of C cannot change the value of any variant. Thus, the variant of a liveness property will be required to decrease strictly for a subset of methods with side eects. Consequently, when assigning a liveness property to a Java class, the user is asked to specify a variant V and a set M of progress methods. This extension of the Loop operator with V and M , attached to a class C , is denoted Loop C (Q, V, M ).

In order to verify Σ C |= Loop C (Q, V, M ), we need to assume progress of the environment, i.e., that the environment invokes the methods of the subset M .

  haviour annotation: behavior; requires P m ; diverges D m ; ensures Q m ; signals (Exception e) R m ;. In the rest of the paper, P m , D m , Q m and R m respectively denote the requires, diverges, ensures and signals predicates of the behaviour of method m.

Denition 13 (

 13 Progress Hypothesis) For any set of methods M , an execution σ ∈ Σ C satises the progress hypothesis, written σ |= P H(M ), if ∀i. (0 ≤ i < len(σ) ⇒ ∃j. (i ≤ j < len(σ) ∧ m∈M prestate(σ, j, m))).

  This satisfaction relation extends to sets of executions in a standard way. The semantics of Loop C (Q, V, M ) is given by the following denition, where 1 M is the characteristic function of set M , whose value 1 M (m) at m is 1 if m ∈ M , 0 otherwise:

  The empty sequence, whose domain is the empty set, is denoted . A sequence σ is innite if dom(σ) = N, nite otherwise. The length len(σ) of a sequence σ is n if it is nite and if dom(σ) = [0, ..., n -1], ω otherwise. The last element last(σ) of a sequence σ is σ(len(σ) -1) if this sequence is nite and nonempty, ω otherwise. We use S * , S + , S ω , S * ω and S +ω to respectively denote the sets of nite, nonempty nite, innite, nite or innite, and nonempty nite or innite sequences.

  Java subset is given in Def. 4 as a sequence of memory states, dened in Def. 3.A component is a Java class dening a set of methods and a set of attributes and ghost variables. The class can be annotated with JML annotations as invariant, constraint and behavior. A behaviour is a method annotation. A class can also contain ghost variables and set annotations. A component is, therefore, an annotated class in Java/JML dened as follows:Denition 1 (Annotated Class) An annotated class C is a tuple (V C , I C , C C , M C ) where V C is the set of attributes and ghost variables of the class, I C is a set of JML invariants, C C is a set of JML constraints and M C is the set of all method names of the class except the constructor i

	4.2	Java Subset Semantics
	In this section Denitions 1 and 2 describe the Java/JML components that we consider. Then an execution
	semantics of a

condition. It is assumed that the annotated class is consistent, i.e. each method m leads to a state that satises either its ensures condition if m does not diverge and does not raise an exception or the signals predicate if it raises an exception. C . A method named m in M C is dened by a tuple (behavior m , paramList m , body m ) where behavior m is the JML specication of a canonical behaviour, paramList m is its set of parameters and body m is the Java program that implements m.

  We suppose that expressions are side-eect free and do not contain method calls. They are denoted E, E i . JML predicates are boolean expressions dened over attributes, ghost variables and values of their types. Some predicates, for example in the constraint or ensures clauses, are pre-/post-predicates using the values of variables in the previous state by the \old notation. Let P be a JML predicate and s, s be two memory states. If P does not contain the keyword \old, s |= P denotes that eval(E, s) = true. Otherwise, (s, s ) |= P denotes that the evaluation of P w.r.t. the states s and s is true. The subterms t of P appearing as \old(t) in P are evaluated in the state s, and the subterms t that are not included in the keyword \old are evaluated in the state s .Intuitively, we dene the semantics of a Java statement T as the execution s T that is generated by the execution of T from the memory state s of STATE. An execution is a sequence of memory states, i.e. an element of STATE +ω .

  Consider the set T of executions starting from any memory state in STATE. This set is related to the unique execution s T after a given state s by T = {s.σ | s ∈ STATE ∧ σ ∈ s T }. while(P ){T } could be dened in the sequence set lattice from Prop. 2 as the least xpoint of the endofunction W dened by

2. The trouble is that this denition of (λs. s while (P ){T } ) is circular. The question remains whether this equation admits a solution and, if it admits more than one, which one should be retained as the right denition. A basic answer is to dene this solution as a xpoint over an adequate lattice.

  11, we use the predicate mp(σ, j, m, i) that is true if σ(j) is the matching post-state of the pre-state σ(i) (Def. 10). Denition 10 (Matching Post-State of a State for a Method in an Execution) The j th state of σ ∈ Σ +ω C is the matching post-state of the i th state of σ for method m, denoted mp(σ, j, m, i), if poststate

  the predicate P m of the requires clause is satised by the pre-state of the method m, that implies:If D m does not hold (¬D m ), then the method must terminate, i.e., it must have a poststate. Moreover, if it is a normal termination (σ(j)(excp)), the predicate Q m of the ensures clause must be satised between the pre-state and the post-state, and the predicate R m of the signals clause must be satised otherwise (see the case ¬D m in (3)).

  liveness property Loop(Q) declared in a class C must hold for every object o of type C . For the sake of simplicity, C is assumed to have no static attribute. Thus Q is a JML predicate with variables among the (non-static) attributes of C . The satisfaction of Loop(Q) on an execution of Σ C intuitively means that if, during the execution, any instance of the class C is in a state satisfying Q, then it is always possible to reach a state satisfying ¬Q by invoking methods of C on this instance. In other words, C satises the liveness property Loop(Q) if Σ C |= Loop(Q).

Acknowledgements

We would like to thank Pierre Lescanne for his helpful advice, Marieke Huisman for her interesting and helpful comments and suggestions to improve this work, and the anonymous referees for their corrections, comments and advice.

Research partially funded by the French National Research Agency, ANR-06-SETI-017 TACOS.

The variant-based liveness proof method is summarised in the following proposition: Proposition 4 For any execution σ ∈ Σ C satisfying the progress hypothesis P H(M ), if σ |= Loop C (Q, V, M ) then σ |= Loop(Q).

Approximation with JML Annotations

This section shows how to use existing JML tools for verifying liveness properties on a class in isolation.

The idea is to replace the liveness clause with standard JML annotations, whose satisfaction is sucient

Verication of the Loop C (Q, V, M ) property is quite similar to a termination proof. As long as Q holds, it must be possible to invoke a method of M , and methods in M must decrease the variant V . Here we propose proof obligations inspired from [START_REF] Burstall | Program Proving as Hand Simulation with a Little Induction[END_REF] expressed as JML annotations. These proof obligations guarantee the satisfaction of the Loop C (Q, V, M ) property by the executions of the class C in isolation.

Let A 1-5 be the following set of JML annotations:

(Pm ==> !Dm);

(A5)

Remember that JML invariants have to hold on all visible states, and JML constraints have to hold between any two successive visible states [START_REF] Leavens | JML Reference Manual[END_REF]. These annotations A 1-5 relate to Q, V , M , and a class C and its methods as follows:

A 1 The variant V is actually greater than zero, it is a function returning a natural number.

A 2 As long as Q holds, the variant V must decrease when a method in M is executed.

A 3 As long as Q holds, the variant V must not increase when a method of C is executed.

A 4 As long as Q holds, there should always be a method in M that may be called, i.e., whose precondition P m (in the clause requires P m ) holds. This ensures the deadlock-freeness of the system.

A 5 As long as Q holds, all callable methods must not diverge, according to the clause diverges D m .

This ensures the non-divergence of the system.

In the rest of the paper, σ :

Proof 1 There are two cases:

1. If σ ∈ Σ C is a nite execution, the denitions in Sect. 4 imply that last(σ) |= P m for any method m in M C , and that last(σ) is the prestate of no method. That falsies P H(M ) for any

2. If σ is an innite execution, the proof is by contradiction. Suppose there exists σ ∈ Σ C such that σ |= Loop C (Q, V, M ). By Def. 13 and 14,

and there are some i, 0 ≤ i < len(σ) -1 and some method m ∈ M , s.t. σ(i) |= Q and

Since σ ∈ Σ C , by the progress hypothesis (Def. 13), we have:

The above property being true for each index k ≥ 0, it is also the case for each index k ≥ i:

Independently, from the semantics of Java statements (Def. 4) and the denition of pre-states (Def. 6), we derive:

On the one hand, from (3) and ( 4), we obtain:

On the other hand, from (2) and (A 5 ), we have:

Then, from ( 5) and ( 6), we obtain:

By Def. 11 (Fig. 3), when using default values [START_REF] Leavens | JML Reference Manual[END_REF] of all but D m of the behavior clause on σ above, item (3) results in:

By (A 2 ), [START_REF] Burdy | Java Applet Correctness: a Developer-Oriented Approach[END_REF] and transitivity of history constraints (Def. 11, item (2) in Fig. 3), we obtain:

By a similar reasoning, we also obtain, from (A 3 ):

Consequently, from [START_REF] Burstall | Program Proving as Hand Simulation with a Little Induction[END_REF] and [START_REF] Cousot | Constructive design of a hierarchy of semantics of a transition system by abstract interpretation[END_REF] one deduces that the variant V decreases innitely during the execution. And so, A 1 cannot be established. A contradiction.

Liveness Temporal Patterns

In [START_REF] Groslambert | JML-based Verication of Liveness Properties on a Class in Isolation[END_REF], we have presented a way to verify liveness properties expressed with the Loop C operator. This section presents a practical context of Java/JML verication where this verication method is applied.

Along the line of helping Java programmers in writing formal specications, Trentelman and Huisman [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF] proposed a temporal extension of JML inspired by the pragmatic work of the SanTos Specication Pattern Project [START_REF] Dwyer | Patterns in property specications for nite-state verication[END_REF]. We refer to this temporal extension of JML as JTPL, for Temporal Pattern Language, prexed by a `J' to denote its adaptation to Java. The semantics of temporal formulae in JTPL and translation rules into JML annotations are detailed in [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF] for safety properties and in [START_REF] Bellegarde | Verication of liveness properties with JML[END_REF] for liveness properties. This section denes a verication technique for liveness properties expressible in JTPL, a problem left open by Trentelman and Huisman [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF]. This verication is performed by translating these properties into the Loop C operator.

Language Overview

JTPL provides the user with patterns to express common temporal requirements of Java classes. Moreover, the language deals with normal and abnormal method terminations. JTPL is based on the notion of trace property which is either always P , eventually P , or the conjunction or disjunction of two trace properties. always P is true on an execution σ if P holds on every state of σ. eventually P is true on an execution σ if P holds on at least one state of σ.

It is often useful to reduce the scope of a trace property, i.e. specifying it only for subparts of an execution. This is made possible by the notion of event. An event can be: (i) m called, denoting that the method m has been invoked; (ii) m normal, denoting that the method m has terminated normally, i.e., without throwing any exception; (iii) m exceptional, denoting that the method m has terminated by throwing an exception; or (iv) m terminates, denoting that the method m has terminated either normally or by throwing an exception. Now, a temporal property in JTPL is inductively dened as follows: let E be a disjunction of events, C a trace property and T a temporal property. A temporal property can be either: (a) after E T , which is true on an execution σ if the sux of σ starting after each occurrence of an event in E satises the temporal formula T ; (b) before E C, which is true on an execution σ if the prex of σ ending with each occurrence of an event in E satises the trace property C; (c) C until E, which is true on an execution σ if an event in E occurs and if the trace property C is satised on the segment of σ ending with an event in E; (d) C unless E, which is true on an execution σ if an event in E occurs and the trace property

C is satised on the segment of σ ending with an event in E, or the trace property C is satised on the whole execution σ and E never happens; or (e) between E E C, which is true on an execution σ if the temporal formula after E (C until E ) holds on σ, or (f ) a trace property C.

Safety and Liveness Characterisation

The properties described by this extension of JML are either safety properties or liveness properties. The following proposition makes it possible to distinguish them syntactically:

Proposition 6 (Characterisation of Safety and Liveness Properties) The properties containing only the keywords after, before, unless and always are safety properties. The properties containing the keyword eventually i they contain the keyword before also are safety properties. The other properties are liveness properties.

For liveness properties, the verication is based on the decrease of a well-founded variant given by the user. Therefore, we propose to extend the syntax of liveness formulae with the following clause:

In the above clause, <JMLProp> is a JML predicate which is an optional local invariant -like a loop invariant -that can help the proof, <JMLExpr> is the variant expression (its type is a natural number), and <Methods> is a list of Java method names.

Back to the Example

Using JTPL formulae, one can express the following properties on the Buffer example (Fig. 1 Sect. 2):

1. After the invocation of storeData (after storeData called), the variable customized is always true, expressed in JTPL as follows:

after storeData called always customized;

(S) 2. After starting a transaction, i.e., after normal termination of the method begin (after begin normal), a state where trDepth is false must eventually be reached.

after begin normal eventually !trDepth under variant getBufferLess() for begin, commit, abort, write;

(L) Property S is a safety property and property L is a liveness property. Notice that in (L), the event is begin normal and not begin called since a buer transaction starts only when the method begin terminates normally. Notice also that since (L) is a liveness property, the user has to give a variant and a set of progress methods with the JTPL clause under variant ... for. Here, the variant corresponds to the free space in the Buffer, and the for clause contains a list of methods that can potentially modify the value of the variant. So, storeData is not in the list.

Embedding Liveness Properties into the Loop Clause

This section presents a translation of a JTPL liveness property into a Loop C clause completed with other JML annotations. Firstly, we present the translation for the basic after E eventually P liveness property. Then, we generalise to the other JTPL liveness properties.

Let us consider a temporal formula of the form:

after E eventually P under variant V for M .

To translate liveness JTPL properties, like [START_REF] Dijkstra | On weak and strong termination[END_REF], into a Loop C clause, one needs to observe whether a par- ticular event has already occurred or whether a state satisfying a predicate has already been reached. For that, we dene a witness primitive, denoted JML(X 1 , X 2 ), where X 1 and X 2 are either JML predicates or JTPL events. Intuitively, given an execution σ, JML(X 1 , X 2 ) is satised on all states of σ between the states satisfying X 1 and X 2 .

Denition 15 (witness Primitive) Let σ be an execution and i a natural number between 0 and

The witness primitives are expressed by JML ghost variables that are assigned w.r.t. events occurring in the formula. The general rules can be easily derived from the following examples:

Example 1 (Ghost Variables Generation for S) The ghost variable witness_S corresponds to the event storeData called of S. It is initially declared with the value false (see annotation S a in Fig. 5)

and it is set to true when the method storeData is called (see annotation S b ). So, in each state after the event storeData called, the value of the ghost variable witness_S is true, i.e., witness_S is true exactly with the scope of the property.

Example 2 (Ghost Variables Generation for L) The ghost variable witness_L, corresponding to the event begin normal of the temporal property L is also declared with the value false (annotation L a in Fig. 5). The ghost variable witness_L is assigned using a try {try {T 1 } catch {T 2 }} finally {T 3 } statement (see annotation L b ). Notice that in the case of exception, the caught exception is re-thrown.

The reader can see that witness_L is set to true only when begin normal occurs. The ghost variable witness_L is set to ¬trDepth again by adding a set statement (annotation L c ) to each method.

Thanks to an adequate witness, one can give a Loop C clause ensuring property [START_REF] Dijkstra | On weak and strong termination[END_REF]. Using the semantics of JTPL in [START_REF] Bellegarde | Verication of liveness properties with JML[END_REF] and the semantics in Sect. 4, one can show that property [START_REF] Dijkstra | On weak and strong termination[END_REF] holds on the execution σ if σ |= Loop C (JML(E, P ), V, M ).

In a similar way, the other JTPL liveness patterns can be translated into JML annotations (using the Loop C clause) by the rules given in Fig. 4. For each Loop C (Q, V, M ), the local invariant J is expressed by an invariant clause invariant Q ==> J. The safety part of the property is also translated into an invariant.

Example 3 (Generation of annotations for L) The JML translation of L is

Loop C (witness_L, getBufferLess(), {begin, commit, abort, write}).

The corresponding annotations are displayed in Fig. 5 (see annotations L loop ). Notice that, since no method of Buffer diverges, annotation A 5 does not appear.

JML Annotation Generator

The automatic generation of JML annotations for safety properties in [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF] and for liveness properties in Sect. 5 has been implemented in a tool, called JAG (for JML Annotation Generator) [START_REF] Giorgetti | JAG: JML Annotation Generation for verifying temporal properties[END_REF]. The JAG 0.1 release parses a Java le -possibly already JML annotated -with the JML parser included in the Common JML tools and takes a le containing temporal formulae as other input. JAG is freely available from page http://jag.univ-fcomte.fr.

Translating Temporal Formulae into Intermediate Primitives. The tool reduces each temporal property into one or more intermediate primitives, like the witness primitive, that are semantically equivalent [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF][START_REF] Bellegarde | Verication of liveness properties with JML[END_REF]. These primitives are an internal format which is independent of the JML syntax, allowing an easy extension of the annotation generation to other specication languages, such as Spec .

Translating Example 4 (Invariant Generation for S) The invariant for S is displayed in Fig. 5 (annotation S c ).

It means that when the variable witness_S is true, i.e., after the rst occurrence of storeData called, the predicate must be true -the denition of property S.

Trace Preservation. The tool is able to keep the trace of the generated annotations, i.e. it is possible, given a generated annotation, to nd the original intermediate primitive and the original temporal property.

Experiments. Since the generated output le contains standard JML annotations, it can be used with other JML tools [START_REF] Burdy | An Overview of JML Tools and Applications[END_REF] to validate or prove the temporal formulae. For instance, Table 1-where PO stands for Proof Obligation -summarises the results we have obtained with the JACK tool [START_REF] Burdy | Java Applet Correctness: a Developer-Oriented Approach[END_REF]. All the 277 POs in 4th column have been proved either fully automatically (for 274 POs) or interactively (for remaining 3 POs by enforcing invariants) with the B4free tool as a back-end theorem prover.

TransactionSystem and AtmTransaction are two academic examples. TransactionSystem is adapted from [START_REF] Trentelman | Extending JML Specications with Temporal Logic[END_REF] and inspired by the JavaCard transaction mechanism, that ensures that every transaction in a smart card is atomic. AtmTransaction implements a transactional mechanism between a smard card and a terminal. Notice that our theoretical contributions have been applied not only to that academic examples but also to the Demoney system, a Java Card Electronic Purse application we have developed in the framework of an industrial collaboration with Trusted Logic 2 , via the ACI GECCOO project. For this application 3 , we wrote over 500 lines of JML annotations.

2 http://www.trusted-logic.com/ 3 whose demonstrative electronic purse -card specication is available at http://www.doc.ic.ac.uk/ siveroni/secsafe/.

Moreover, we have successfully used the JAG tool for the following purposes:

• Verication of the correctness of the Java code w.r.t. the JML annotations with the proof obligation generators Jack [START_REF] Burdy | Java Applet Correctness: a Developer-Oriented Approach[END_REF] and Krakatoa [START_REF] Marché | The Krakatoa tool for certication of Java/Java Card programs annotated in JML[END_REF];

• Validation of a JML model with JML-TT [START_REF] Bouquet | JML-Testing-Tools: a symbolic animator for JML specications using CLP[END_REF];

• Formal verication of a JML model with the JML2B method [START_REF] Bouquet | Checking JML specications with B machines[END_REF];

• Test generation and Runtime Assertion Checking with the test generators Tobias [START_REF] Ledru | Filtering TOBIAS Combinatorial Test Suites[END_REF],

Jartege [START_REF] Oriat | Jartege: A Tool for Random Generation of Unit Tests for Java Classes[END_REF] and JML-TT [START_REF] Bouquet | Automated Boundary Test Generation from JML Specications[END_REF].

Test generation and Runtime Assertion Checking using JAG has been studied on an industrial Java Card application [START_REF] Bouquet | Safety property driven test generation from JML specications[END_REF].

Conclusion and Future Works

This paper presents a way to verify liveness properties on Java classes in isolation by generating appropriate JML annotations. This requires that the user specify a variant for the verication of a Loop clause to which liveness properties are reduced. The generated JML annotations are veried (or validated) with any tool handling JML. The JAG tool implements this translation. It has been used for several toy examples and a Java Card Electronic Purse Specication (over 500 lines of JML).

To the best of our knowledge, this is the rst attempt to verify liveness properties for potentially innite-state systems using a translation into JML. We are working on extensions of JAG to other temporal properties. In particular, we currently address the verication of properties expressed by Büchi automata.

Assuming that a liveness is established on the class in isolation, another challenge is to provide techniques for verifying that the (single-or multi-threaded) environment eectively satises a progress hypothesis.

List of Figures //@ ghost boolean trDepth = false; //@ invariant position >= 0;

/*@ constraint @ position > \old(position) @ for write; @*/ /*@ normal_behavior @ requires customized == false; @ requires l > 0; @*/ void storeData(int l){ len = l; customized = true; } byte[] getStatus(){ return status; } int getBufferLess(){ return len -buffer.length; } /*@ normal_behavior @ requires trDepth == false; @ requires customized == true; @ also @ exceptional_behavior @ requires customized == false; @ signals (Exception e) true; @*/ void begin() throws Exception{ if (customized == false) { throw new Exception(); } buffer = new byte[len]; //@ set trDepth = true; } /*@ normal_behavior @ requires trDepth == true; @ requires customized == true; @*/ void commit(){ status = buffer; position = 0; //@ set trDepth = false; } /*@ normal_behavior @ requires trDepth == true; @ requires customized == true; @*/ void abort(){ position = 0; //@ set trDepth = false; } /*@ normal_behavior @ requires trDepth == true; @ requires customized == true; @ requires position @ + b.length <= len; @ diverges false; @ ensures position <= len; @ ensures position == @ \old(position)+b.length; @*/ void write( (

where postcontract(σ, j, m, i) = (¬σ(j)(excp) ⇒ (σ(i), σ(j)) |= Qm) ∨ (σ(j)(excp) ⇒ (σ(i), σ(j)) |= Rm) Temporal Formula Translation eventually P under invariant J Loop C (¬JML(P, false), V, M ) variant V for M //@ invariant ¬JML(P, false)==>J; always P until E under Loop C (¬JML(E, false), V, M ) invariant J variant V for M //@ invariant ¬JML(E, false)==> P && J; eventually P under invariant J Loop C (¬JML(P, false), V, M ) variant V for M unless E //@ invariant JML(E, false)==>JML(P, false); //@ invariant ¬JML(P, false)==>J; eventually P until E Loop C (¬JML(E, false), V, M ) under invariant J //@ invariant JML(E, false)==>JML(P, false); variant V for M //@ invariant ¬JML(E, false)==>J; after E1 always P until E2 Loop C (JML(E1, E2), V, M ) under invariant J variant V for M //@ invariant JML(E1, E2) ==> P && J; after E eventually P under Loop C (JML(E, P ), V, M ) invariant J variant V for M //@ invariant JML(E, P ) ==> P && J; after E1 eventually P until E2 under Loop C (JML(E1, E2), V, M ) invariant J variant V for M //@ invariant JML(E2, E1)==>JML((JML(E1, E2) ∧ P ), E1)&& J; after E1 eventually P under Loop C (JML(E1, P ), V, M ) invariant J //@ invariant JML(E2, E1)==>JML((JML(E1, E2) ∧ P ), E1); variant V for M unless E2 //@ invariant JML(E1, P )==>J //@ ghost boolean witness_L = false; (La) /*@ invariant witness_S @ ==> customized; @*/ (Sc) //@ invariant getBufferLess() >= 0; /*@ constraint witness_L ==> @ getBufferLess() < \old(getBufferLess()) @ for begin,commit, abort, write; @*/ /*@ constraint witness_L ==> @ getBufferLess() <= \old(getBufferLess()) @*/ /*@ invariant witness_L ==> ( @ (trDepth == false && customized == true) @ (trDepth == true && customized == true) @ (trDepth == true && customized == true @ && position + b.length <= len)) @*/