Victor L J L Thijssen

Ruben Postel

Ricardo J M G E Brandwijk

Ruud P M Dings

Irina Nesmelova

Sietske Satijn

Nicole Verhofstad

Yusaku Nakabeppu

Linda G Baum

Jeroen Bakkers

Victor Ljl Thijssen

Ricardo Jmge Brandwijk

Ruud Pm Dings

Kevin H Mayo

Françoise Poirier

PhD. Arjan W Griffioen
email: aw.griffioen@path.unimaas.nl

Galectin-1 is essential in

Keywords:

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

An adequate vasculature is a prerequisite for tumors to grow, and the need for neovessel formation (or angiogenesis) provides a target for treatment of cancer (1). Endothelial cells (EC) that line the tumor vasculature are particularly suitable target cells for therapeutic approaches since they are easily accessible to agents delivered via the blood (2). However, to affect only tumor vasculature, specific targets on angiogenically active EC are essential. To date, only a few targets of tumor vasculature have been identified (3).

We recently developed the specific angiostatic peptide anginex that inhibits tumor growth through specific inhibition of angiogenesis (4)(5)(6). Although a broad profile of activities of anginex is known, such as prevention of EC adhesion and induction of apoptosis, the molecular target on tumor EC was never identified. In a receptor finding study using a yeast two-hybrid screening approach, we identified galectin-1 as a target protein of anginex.

Galectin-1 belongs to a family of carbohydrate binding proteins that share a conserved carbohydrate recognition domain (CRD) of approximately 130 amino acids (7)(8)(9). Over a dozen mammalian galectins have been described (10,11) and members of this family are expressed in a wide range of species, suggesting an important role for galectins in basic cellular mechanisms.

Galectins can be secreted, and depending on the cell type or state of differentiation, they have been found in the nucleus, in the cytoplasm, or in the extracellular matrix. It has been proposed that galectin-1 mediates cell adhesion and migration (12), and is involved in several processes including proliferation (13), apoptosis (14), and even mRNA splicing (15). The role of galectin-1 in EC function or in vascular biology has not been extensively studied.

Here, we describe the function of galectin-1 in the angiogenesis. We provide direct functional evidence that galectin-1 is required for tumor angiogenesis and for outgrowth of tumors. Furthermore, we show that galectin-1 is the target for the potent angiogenesis inhibitor anginex, thus establishing galectin-1 as an important target for anti-cancer therapy.

Results

Galectin-1 binds the angiostatic peptide anginex.

The goal of the present study was to identify the receptor of anginex, an angiogenesis inhibitor which has previously been shown to specifically target tumor endothelial cells (EC) (5).

Immunohistochemistry revealed vesicular uptake of anginex by EC within 2 hours (Fig. 1A).

Electron microscopy showed anginex located at the membrane of intracellular vesicles, suggesting receptor-mediated uptake (Fig. 1B). To identify this receptor, yeast two-hybrid (Y2H) analysis was performed. To that end, the recently described artificial anginex gene (16) was cloned in frame with the GAL-4 DNA binding domain of the Y2H bait vector pGBDT7, which was confirmed by Western blotting (not shown). Multiple screens against cDNA libraries of activated EC identified galectin-1 (gal-1) as the receptor for anginex (Suppl. Table 1/Suppl. Fig. 1) which was independently confirmed using three approaches. i) Double staining of anginex treated EC showed co-localization of anginex and gal-1. ii) Analysis of NMR spectra revealed chemical shift changes of certain resonances from gal-1 upon addition of anginex, indicative of a specific molecular interaction. iii) Plasmon resonance spectroscopy (BIAcore analysis) was used to further define the kinetics and stoichiometry of the interaction. Analysis of the binding kinetics revealed a 1:1 Langmuir association with a rate constant (k a ) of ~6.5x10 3 Ms -1 , while the dissociation kinetics followed a biphasic pattern with dissociation rate constants of 4.2x10 -2 s -1 and 5.9x10 -4 s -1 , respectively. These data suggest that dimerized anginex binds to gal-1 and that subsequently the two anginex molecules dissociate as monomers with a K d of 6.4 μM for dissociation of first anginex molecule and a K d of 90 nM for the second molecule. This result is supported by mass spectrometry which displayed a major peak with a mass of 22.8 kD (gal-1 monomer (14.7 kD) + anginex dimer (8 kD) (not shown). The data above show that gal-1 and anginex interact, suggestive of gal-1 serving as receptor for anginex.

Galectin-1 is overexpressed in tumor EC; a crucial role in EC proliferation and migration.

To determine the role of gal-1 in tumor EC biology, we first analyzed gal-1 expression in human tumor blood vessels by immunohistochemistry. While gal-1 is only weakly expressed in EC of normal tissue (colon is shown: Figure 1C, left panels), a strong expression was found in EC of human colon carcinoma (Figure 1C, middle panels) and breast carcinoma (not shown), especially in EC that stained positive for the proliferation marker Ki67. Similar results were observed for a sarcoma type of tumor (Ewing sarcoma) in which the gal-1 staining was almost exclusively observed in vessels (Figure 1C, right panels). These data demonstrate that the amount of gal-1 protein is upregulated in angiogenically active EC. Indeed, growth factor activation of freshly isolated human umbilical vein EC resulted in a significant increase in gal-1 mRNA expression and a concomitant >10-fold induction of gal-1 protein expression (Figure 1D). Furthermore, treatment of activated EC with a gal-1 specific antisense oligodeoxynucleotide (ODN) resulted in inhibition of EC proliferation, while a random ODN had no effect (Figure 1E). Next to EC proliferation, EC migration was also inhibited by treatment with either the gal-1 specific ODN (Figure 1F) or the rabbit polyclonal anti-gal-1 antibody (Figure 1G). These data strongly suggest a role for gal-1 in EC biology.

Galectin-1 is required for coordinated angiogenesis in vivo.

The role of gal-1 in angiogenesis in vivo was first studied in the chick chorioallantoic membrane (CAM). Treatment of the CAM with a rabbit polyclonal anti-gal-1 antibody induced a significant inhibition of microvessel density, similar as previously published for anginex (4-5) albeit less pronounced. Interestingly, treatment caused tortuous and irregular growth of the vessels, suggesting a defect in vascular guidance (Suppl. Fig. 2). For further insight in the role of gal-1 during angiogenesis in vivo, we used the Tg(fli1:egfp) y1 zebrafish model. In this model, EC are marked by expression of green fluorescent protein (GFP) (17). Recently, 3 prototype galectins were described in zebrafish (Lgals1-L1/L2/L3) of which Lgals1-L2 was found to preferentially bind N-acetyllactosamine, similar to human gal-1 (18). Since Lgals1-L1 is not expressed during embryogenesis (18) we only studied the role of the other two prototype galectins in vascular development. Whole mount RNA in situ hybridization at 48 hours post-fertilization revealed specific expression of Lgals1-L2 in the eyes around the lens and in the ventricular zone in the head (Figure 2A). Lgals1-L3 expression was broader and largely overlapped with that of Lgals1-L2 (Figure 2B). Furthermore, cross sections at the level of the midbrain showed co-localization of both Lgals1-L2/-L3 and the EC specific marker VE-cadherin in the retinal vessels (Figures 2C-E) and in the blood vessels in the brain (not shown).

To determine the function of Lgals1-L2 and -L3 on vascular development, morpholino-modified antisense oligonucleotides (MOs) were designed to specifically target either the translation start site (ATG-MO) or the splice donor site (splice-MO). We verified that injection of each splice-MO successfully interfered with the splicing of the respective transcripts (not shown). Injection of either Lgals1-L2 or -L3 ATG-MO induced hemorrhages in the head and in/behind the eyes of the embryos at 2.5 days post fertilization, as detected with a sensitive o-Dianisidine blood staining. Co-injection of both Lgals1-L2 and -L3 MOs resulted in even more severe hemorrhages (Figures 3A-D). Similar results were observed with the splice-MOs (not shown). Confocal scanning laser microscopy in the ventricular zone of Tg(fli1:egfp) y1 zebrafish revealed vascular defects, at the location of the hemorrhages, after co-injection of Lgals1-L2 and -L3 ATG MO.

Compared to untreated zebrafish (Figure 3F), abnormal sprouting and misguidance of vessels clearly appeared in the mid-cerebral area of the Lgals1-L2 and -L3 ATG MO treated animals (Figures 3E-H). Vascular network formation of the middle cerebral-, dorsal longitudinal-, mesencephalic-and anterior cerebral veins was also distorted by both MOs, and most severely in the double knockdown (Figure 3G). The same defects were observed upon co-injection of both splice MOs, indicating specificity of the knockdown defects (Figure 3H), while single injection of each splice MO revealed weaker defects (not shown). Similar to those in the ventricular zone, retinal vessels showed abnormal sprouting and growth in the regions where hemorrhages occurred (not shown). Together with observations from the CAM, results in zebrafish indicate that gal-1 is important in vivo for coordinated vessel outgrowth and vascular network formation.

Galectin-1 facilitates tumor progression through angiogenesis.

The presented results urged us to study the role of gal-1 by analyzing tumor angiogenesis in the gal-1 null mice (19). To compare tumor growth in the presence or absence of gal-1, wild type (gal-1 +/+ ) and null (gal-1 -/-) mutant 129P3/J mice were subcutaneously injected with syngeneic murine F9 teratocarcinoma cells. Three days after injection, a small palpable tumor developed in all mice, suggesting that tumor initiation and initial growth is not dependent on gal-1. However, subsequent tumor growth was significantly abrogated in the gal-1 -/-mice compared to the wildtype animals. Fifteen days after injection, the tumor volumes in the gal-1 -/-mice were approximately 4-fold smaller compared to those in the gal-1 +/+ mice (Figure 4A). As expected, immunohistochemical analysis showed high expression of gal-1 in the EC of tumor vessels in the wild-type animals and no expression in the null mice (Figure 4B). Quantification of microvessel density revealed a significant lower amount of blood vessels in null mice compared to wild-type mice (Figure 4C). In addition, parameters of vessel architecture were decreased (Suppl. Table 2). Since gal-1 has been shown to mediate apoptosis in activated T cells, which could contribute positively to tumor growth (20), we also quantified the amount of peripheral blood leukocytes, and the presence of CD45 + and CD8 + cells in the tumors. There was no significant difference in these parameters between gal-1 +/+ and gal-1 -/-animals (Suppl. Fig. 3) which strongly suggests that, in this particular model, impaired tumor progression in gal-1 null mice largely results from decreased angiogenesis.

Galectin-1 is a target protein for angiostatic therapy.

Because gal-1 was initially identified as a receptor for the angiostatic peptide anginex, we also analyzed the effect of anginex treatment in wild type and gal-1 null mice. In wild-type animals, anginex significantly inhibited tumor growth by approximately 70% (Figure 4D) and vessel density by approximately 55% (Figure 4E), which is comparable with previous observations for anginex in other tumor models (5,21). In gal-1 -/-mice, treatment with anginex had no effect on tumor growth (Figure 4F). In addition, anginex treatment did not significantly affect the number of infiltrating CD45 + or CD8 + cells in the tumors of both the wild type and null mice (Suppl. Fig. 4). These data demonstrate that gal-1 mediates the angiostatic activity of anginex and that gal-1 can serve as a target for angiostatic therapy.

Discussion

The current study is the first to demonstrate that gal-1 is important in tumor angiogenesis and that targeting of gal-1 can be an efficient angiostatic therapeutic strategy. Previous studies have shown that gal-1 is key in two mainstays of cancer. Firstly, gal-1 supports metastasis formation, because it facilitates interactions between tumor cells and endothelial cells (EC) (22,23). Secondly, it protects the tumor against immunity since it can induce apoptosis in tumor infiltrating cytotoxic leukocytes (14,20). This study now reports a critical role in angiogenesis, a third important pillar in tumor growth. Our results reveal a direct role of gal-1 in EC biology. We found a direct involvement of gal-1 in EC proliferation and migration in vitro and in tumor angiogenesis in vivo. While the angiogenesis-independent onset of F9 tumor growth was similar in gal-1 null and wild type mice, the angiogenesis dependent outgrowth of tumors was severely hampered in the null mice. The low microvessel density in the null mice led us to conclude that the abrogated tumor growth is caused by inefficient angiogenesis. It has been shown that gal-1 null mice have subtle neuronal abnormalities that become apparant upon challenge (24,25). In line with this, the effect on angiogenesis also becomes apparent by challenging the mice with a growing tumor. This corroborates with our observations in the CAM and the zebrafish, in which acute interference with gal-1 function also results in aberrant angiogenesis. Obviously, the presence of gal-1 is required for a proper response to an acute stress or pressure on EC biology and angiogenesis. It remains to be investigated whether vascular development in the null mice is indeed normal, or that subtle vascular defects do exist.

We also observed that intervening with gal-1 function results in irregular patterning of the vasculature. The abnormal vessel architecture in the CAM, the zebrafish model, and in knockout mice tumors, suggest that gal-1 is involved in vascular network formation. Recent studies have shown that the development of both vascular and neuronal networks is regulated by the same receptor/ligand pairs, i.e. Robos/Slits, Ephrins/Eph receptors, Neuropilins/Semaphorins, and Netrins/Unc5B (26,27). Interestingly, for gal-1 a role in neuronal pathfinding has already been identified (28). Furthermore, gal-1 null mice show neuronal abnormalities in adulthood (25).

Together with the role of gal-1 in angiogenesis described here, these data strongly suggest that gal-1, as well as other members of the galectin family (galectin-3 (29,30)) are also involved in both neuronal and vascular development.

It has been proposed that galectins can serve as molecular targets for cancer therapy (20,(31)(32)(33). Interestingly, we identified gal-1 as a receptor for the angiostatic peptide anginex.

Anginex has been shown to inhibit tumor growth by inhibition of tumor angiogenesis (4-6). A

previous study reported that transport to the tumor vasculature is facilitated by fibronectin (34).

Our results now show that for the angiostatic activity on EC, galectin-1 is required. Anginex treatment in gal-1 null mice did not result in further inhibition of the already hampered tumor growth, while wild type mice responded as reported previously (5,6). This indicates that gal-1 is essential for the activity of anginex and that gal-1 can indeed serve as a target for angiostatic cancer therapy. We also observed high expression of gal-1 in EC in mouse tumors as well as in human colon and breast carcinomas. There are other reports on the expression of gal-1 in tumor stroma, mainly in studies comparing the expression between normal and cancerous tissues (reviewed by (33)). Elevated stromal expression of gal-1 has been reported in several cancers including cancer of the ovaries (35), breast (36), prostate (37), and colon (38). These results suggest that the increased expression in tumors makes the protein an excellent target for diagnostic or therapeutic purposes.

It is attractive to speculate that, since gal-1 is crucial in several prerequisites for unlimited tumor growth, gal-1 targeting compounds may have multimodal activities. Interfering with gal-1 function could (i) prevent metastasis formation through inhibition of gal-1 facilitated tumor cell-EC interactions (22,23), (ii) abrogate tumor escape from immunity through blockade of gal-1 induced apoptosis in activated T lymphocytes (14,20), and (iii) prevent the execution of tumor angiogenesis (this study). This makes gal-1 an excellent target for cancer therapy.

Materials and Methods

Cell cultures

Human umbilical vein EC (HUVEC) and the human microvascular EC line HMEC were cultured as described elsewhere (5). F9 teratocarcinoma cells (kind gift from Dr. H. Weich) were cultured in RPMI-1640 supplemented with 10% fetal bovine serum, 1% glutamin, 50 U/ml penicillin, and 50 ng/ml streptomycin.

Mouse tumor model

A total of 14 adult 129P3/J gal-1 -/-mutant mice (19) and 17 matched 129P3/J gal-1 +/+ (wild type) mice were used in this study. On day 1, animals were injected s.c. with 3x10 6 syngeneic F9 teratocarcinoma cells. On day 7, anginex treatment (10 mg/kg/day) was started in 7 wild type and 9 mutant mice by daily i.p. injections. Tumor volume and mouse weight were measured daily throughout the experiment. Animals were given water and standard chow ad libitum, and they were kept on a 12-hour light/dark cycle. All experiments were approved by the local ethical review committee.

Knockdown of galectin-1 expression in vitro

Knockdown of gal-1 expression in vitro was obtained using a gal-1 specific antisense oligodeoxynucleotide (hgal1 ODN: GTCACCGTCAGCTGCCATGT). As control, a random nonspecific antisense oligodeoxynucleotide (control ODN: TCCCTAGTGACTCTTCCC) was used. ODNs were renewed every other day.

FACS analysis

FACS analysis of gal-1 protein expression was performed on ethanol fixed HUVEC. Cells were washed in 0.1% BSA/0.01% sodium azide/PBS, incubated on ice with polyclonal rabbit antigalectin antibody (39), and washed with PBS. Next, the cells were incubated with FITC-labeled polyclonal goat anti-rabbit Ig antibody (Dako) and washed with PBS. Five thousand events were acquired for each sample on a FACSCalibur flow cytometer (Beckton Dickinson). All experiments were performed in triplicate.

Migration, proliferation, and CAM assay

Migration, proliferation, and CAM assays were performed as described elsewhere (16). Within each proliferation experiment, treatments were done in triplicate and all proliferation and migration experiments were performed at least three times. For the CAM, two independent experiments were performed (overall n = 13 / treatment group).

Real-time PCR

Total RNA isolation, subsequent cDNA synthesis, and real-time PCR were performed as described previously (40) with primers targeted against human gal-1 (Forward: TGCAACAGCAAGGACGGC; Reverse: CACCTCTGCAACACTTCCA). Primers were purchased from Eurogentec and experiments were performed in triplicate.

Immunohistochemistry

Immunohistochemical staining of anginex uptake was performed on HUVEC cytospins. Cells were acetone fixed and air dried. Following incubation in 1% paraformaldehyde cells were incubated in fetal calf serum after which mouse 2D10 monoclonal anti-anginex antibody (5) was applied in 0.05% Triton X100/PBS. Following incubation with Texas Red labeled goat-anti-mouse Ig antibody, the cells were washed with PBS and mounted in Immumount (Shandon Inc.) supplemented with 1 µg/ml 4',6-diamidino-2-phenylindole (DAPI; Molecular Probes). In the negative control, incubation with the first antibody was omitted. Doublestaining for Ki67 and CD31/34 on paraffin-embedded tissue sections was performed as previously described (41). Tissues from normal colon, colon carcinoma, and Ewing sarcoma were obtained from the stocks of the Department of Pathology, University Hospital Maastricht. For gal-1 staining, paraffin-embedded tissue sections were dewaxed and endogenous peroxidase activity was blocked with 0.3% H 2 O 2 in methanol. Next, the slides were microwave pretreated in citric acid. After blocking with 1% BSA/PBS primary antibody was applied in 0.5%BSA/PBS. Next, biotin-labeled secondary antibody was applied and staining was performed with the StreptABComplex/HRP kit (Dako) according the suppliers protocol. The tissue sections were counterstained with haematoxilin (Merck), dehydrated and mounted in Entellan (Merck). The same protocol was used for EC staining with the EC specific antibody 9F1 (42). Staining for CD45+ and CD8+ cells was performed on frozen tissue sections which were fixed in acetone and air dried. Endogenous peroxidase activity was blocked with 0.3% hydrogen peroxidase/PBS and aspecific binding was blocked with 20% FCS/0.1% Tween20/PBS. Next, the primary antibody (MP33 rat anti-mouse CD45 or 53.6.27 rat anti-mouse CD8) was applied, followed by incubation with biotin labeled secondary antibody. Staining was visualized using the Vectastain ABC kit (Vector Laboratories) and subsequently, sections were counterstained with haematoxylin, dehydrated, and mounted with Entellan. Within each section, the number of positive cells was scored at 4 different locations in a blinded fashion by two different observers. Fluorescent staining of CD31 in murine tumors and subsequent scoring of vessel characteristics was performed as described before (6).

Zebrafish experiments

For in vivo experiments, the previously described Tg(fli1:egfp) y1 zebrafish was used (17). Knockdown of Lgals1-L2 and -L3 expression was achieved by injection of specific morpholinomodified antisense oligonucleotides (MOs; Genetools) into 1-cell stage embryos (43). The following MOs were used: Lgals1-L2 ATG-MO, 5'-GTATAAGCACACCGGCCATTTTGAC-3';

Lgals1-L3 ATG-MO, 5'-AAGATCCCAGGCTAAGGACGTCATT-3'; Lgals1 L2 splice-MO, 5'-TTGTAATATACTCACGGCCATTTTG-3'; Lgals1 L3 splice-MO, 5'-ATGTCTGTACTCACGCATCACAGCC-3'. Before 24 hours post-fertilization (hpf), 1-Phenyl-2-thiourea (PTU, 0.002%) was added to prevent pigment development. For imaging, dechorionated embryos were anesthetized with 0.003% tricaine methanesulfonate and mounted in 2% low melting agarose. Confocal scanning microscopy was performed using a Leica TCS NT.

For whole mount blood staining, dechorionated and PTU treated embryos were incubated in 40% EtOH, 0.01M NaAc pH5.2, 2.0% H 2 O 2 , in the presence of 0.8 mg/ml o-dianisidine. Following rehydration in a graded series of EtOH/PBST the embryos were stored in 50% glycerol at 4°C.

Whole mount in situ hybridization on zebrafish embryos was carried out as previously described (44). For VE-cadherin riboprobe synthesis we used the previously published plasmid (45). For Lgals1-L2 antisense probe synthesis RZPD clone IMAGp998D0710947Q3 (in pSPORT1) was linearized with BamHI and transcribed with T7 RNA polymerase. Zebrafish Lgals1-L3 was cloned from RZPD clone IMAGp998J1712051Q3 into pBluescript KS giving rise to lgal1-L3/pBs. For lgal1-L3 antisense probe synthesis, plasmid lgal1-L3/pBs was linearized with Acc65I and transcribed with T7 RNA polymerase. For sectioning, the embryos were embedded in Technovit 8100 (Heraeus Kulzer, Wehrheim Germany). Seven µM thick sections were cut and counterstained with neutral red dye.

Figure 1 .

 1 Figure 1. Galectin-1 binds to anginex and galectin-1 expression is enhanced in activated EC

Figure 2 .

 2 Figure 2. Expression of zebrafish Lgals-1 L2 and Lgals-1 L3.

Figure 3 .

 3 Figure 3. Loss of zebrafish galectin-1 L2 and L3 results in hemorrhages in the brain and

(

  H) Co-injection of the Lgals-1 L2 and L3 splice-MO shows similar defects in angiogenic sprouting of the brain vessels. DLV, dorsal longitudinal vein; MCeV, middle cerebral vein; MsV mesencephalic vein; MtA, metencephalic artery; PCeV, posterior cerebral vein.

Figure 4 .

 4 Figure 4. Hampered tumor growth and lack of responsiveness to anginex in galectin-1

Acknowledgements

The authors are grateful for excellent assistance of S Chocron for in situ hybridizations and sectioning, Drs. P Frederik and D van der Schaft for the EM experiments, Dr. H Weich for providing the F9 teratocarcinoma cells, Dr. A Hamann for providing the 9F1 antibody, Drs. W Roeffen and M Roestenberg for their help with the BIAcore experiments, Drs. C Baeten and F Hillen for CD8/CD45 scoring, and Drs. S Ekker, Dr. S Schulte-Merker and Dr. D Stainier for providing reagents. We thank M Pang for the production of recombinant gal-1 and Dr. W Buurman for critical reading of the manuscript. This research was supported in part by a grant from the National Institutes of Health USA (CA 096090) to KHM. AG was supported by a grant from the Technology Foundation STW, applied science division of NWO and the technology program of the Ministry of Economic Affairs. FP was a recipient of grants from GEFLUC, ARC and LN CC.

LGB was a recipient of a grant from the Cancer Research Institute.

Statistics

All data are shown as mean with standard error except where indicated otherwise. Data from in vitro proliferation, real-time PCR, CAM assay, FACS analysis, and CD45/CD8 scores were analyzed using the Mann-Whitney U test. Tumor growth curves and migration assay data were analyzed using 2-way ANOVA. The Student's t-test was used to analyze the vascular parameters.

All values are two-sided and P-values<0.05 were considered statistically significant. Two-way ANOVA was performed in Graphpad Prism 3.0 (Graphpad Software Inc.). All other statistical computations were performed in SPSS 10.0.5. (SPSS Inc.).

Supplementary data

Results

Multiple screens against cDNA libraries of activated EC identified galectin-1 (gal-1) as the receptor for anginex (Suppl. Table 1). Galectin-1 was found most frequently (15%) while no other members of the galectin family were identified. The identification of fibronectin, of which a previous study reported that it facilitates transport of anginex to the tumor vasculature (1), confirmed the validity of the approach.

The interaction was confirmed using three approaches i) Double staining of anginex treated EC showed co-localization of anginex and gal-1 (Suppl. Fig. 1A). ii) Analysis of NMR spectra revealed chemical shift changes of certain resonances from gal-1 upon addition of anginex, indicative of a specific molecular interaction (Suppl. Fig. 1B). iii) Plasmon resonance spectroscopy (BIAcore analysis) was used to further define the kinetics and stoichiometry of the interaction. To that end, gal-1 was immobilized on a BIAcore sensor chip which was verified with a rabbit polyclonal anti-gal-1 antibody (Suppl. Fig. 1C). Addition of anginex resulted in a concentration dependent change in resonance response units (Suppl. Fig. 1D). Analysis of the binding kinetics revealed a 1:1 Langmuir association with a rate constant (ka) of ~6.5x103 Ms-1, while the dissociation kinetics followed a biphasic pattern with dissociation rate constants of 4.2x10-2 s-1 and 5.9x10-4 s-1, respectively (Suppl. Fig. 1E).

The in vivo role of gal-1 in angiogenesis was studied in the chick chorioallantoic membrane (CAM). Treatment of the CAM with a rabbit polyclonal anti-gal-1 antibody induced a significant inhibition of microvessel density, similar as previously published for anginex albeit less pronounced (Suppl. Fig. 2A). Interestingly, treatment caused tortuous and irregular growth of the vessels, suggesting a defect in vascular guidance (Suppl. Fig. 2B).

In the tumors of gal-1 null mice, several parameters of vessel architecture were decreased, indicative of a less comples and less developed vasculature (Suppl. Table 2).

Galectin-1 has been shown to mediate apoptosis in activated T cells, which could also contribute positively to tumor growth (2). To determine whether this also occurred in our tumor model we quantified the amount of peripheral blood leukocytes and the presence of CD45+ and CD8+ cells in the tumors. In our teratocarcinoma model there was no significant difference in these parameters between gal-1+/+ and gal-1-/-animals (Suppl. Fig. 3) which strongly suggests that, in this model, impaired tumor progression in gal-1 null mice largely results from decreased angiogenesis.

In addition, anginex treatment did not significantly affect the number of infiltrating CD45+ or CD8+ cells in the tumors of both the wild type and null mice (Suppl. Fig. 4).

Materials and Methods

Yeast two-hybrid screening

Yeast two-hybrid screening was performed using the MATCHMAKER GAL4 Two-Hybrid System 3 (Clontech) according to the manufacturers instructions. In short, the artificial anginex gene (3) was PCR amplified and cloned into bait vector pGBKT7 in frame with the GAL4 DNA binding domain (pBD-Ax). The construct was tested for absence of transcriptional activation and toxicity. Subsequently, yeast AH109 cells were co-transformed with pBD-Ax, SmaI-linearized prey vector (pGADT7), and a cDNA library which was generated from activated HUVEC mRNA. Following growth on media plates selective for reporter gene activation, prey plasmids from positive yeast colonies were isolated using CHROMA SPIN-1000 columns (Clontech), shuttled into E.Coli, and sequenced using an automatic DNA-sequencer (AbiPrism377, Applied Biosystems). Confirmation of interaction was performed by targeted transformation of the specific constructs using the small-scale yeast transformation protocol as described in the yeast protocol handbook (Clontech).

Surface Plasmon Resonance

Real-time monitoring of molecular interactions was performed at 25°C using the BIAcore 1000 biosensor system (BiaCore) according to the manufacturer's instructions. In short, recombinant human galectin-1 (4) was immobilized to a CM5 sensor chip (BiaCore) via primary amine groups using the Amine Coupling Kit (BiaCore). For interaction analysis, 20 µl sample was diluted to various concentrations in HBS-EP (Biacore) and was injected using the KINJECT command at a flow rate of 30 µl/minute after which the flow cells were regenerated by injection of 20 µl regeneration buffer (10 mM glycine-HCl, pH 2.0). Association-rate (k a ) and dissociation-rate (k d ) constants were obtained by analysis of the sensograms using the Biaevaluation software, version 3.2. All measurements were performed at least in duplicate at all concentrations and the experiment was performed in duplo.

NMR Spectroscopy

For NMR measurements, 5 mg of recombinant human galectin-1 (4) was dissolved in 600 μl of 10mM potassium phosphate buffer made with 95%/5% H 2 O/D 2 O at pH 5.2. Freeze-dried anginex was dissolved in 10 μl of the same buffer and added to the galectin sample at the molar ratio of 1:2 (anginex:galectin). 2D-homonuclear TOCSY spectra (5) with WATERGATE for water suppression, were acquired on a Varian UNITY Plus-600 NMR spectrometer at 30°C. 2048 complex data points along t2 and 256 increments along t1 dimensions over a spectral width of 9000 Hz, were collected. A mixing time of 50 ms was used. Data were processed using a Gaussian window function and the program NMRPipe (6).

Electron Microscopy

For electron microscopy, HUVEC were grown on gelatin coated and glutaraldehyde fixed thermanox cover slips in normal HUVEC culture medium supplemented with 75 µM anginex. Subsequently, cells were fixed with 1% paraformaldehyde, and localization of anginex by jet freezing and freeze substitution was performed as described previously (7), using polyclonal rabbit anti-anginex antibody in combination with immunogold labeled goat anti-rabbit antibody (Aurion).

Supplementary Table 1. Results of yeast two-hybrid screening with anginex as bait.

Clone name number of clones

Galectin-1 9

Methallothionein 2A 3 b Clones of which the interaction has not been confirmed or that have not been identified by sequencing. On the last day of the experiment, tumors were excised. Tumors without apparent widespread necrosis were embedded in tissue freezing medium (Miles Inc.) and snap frozen in liquid nitrogen. Preparation and procedures were done as described earlier(8).

Supplementary

a After binarization of the images from CD31-staining, microvessel density was estimated by scoring the total number of white pixels per field.

b Mean number of vessel end points as determined after skeletonization of the images(8).

c Mean number of vessel branch points/nodes per image.

d Mean total vessel length per image.

All results are expressed as mean pixel counts per image ± standard error from 20 images. # p<0.05 vs. wildtype.

Supplementary figure legends

Supplementary Figure 1. Confirmation and characterization of the interaction between galectin-1 and anginex.

Supplementary figure 1

Supplementary figure 2 Supplementary figure 3 Supplementary figure 4


Barbara Kordy
email: barbara.kordy@uni.lu

Marc Pouly
email: marc.pouly@hslu.ch

Patrick Schweitzer
email: patrick.schweitzer@uni.lu

A Probabilistic Framework for Security Scenarios with Dependent Actions

Keywords:

This work addresses the growing need of performing meaningful probabilistic analysis of security. We propose a framework that integrates the graphical security modeling technique of attack-defense trees with probabilistic information expressed in terms of Bayesian networks. This allows us to perform probabilistic evaluation of attackdefense scenarios involving dependent actions. To improve the efficiency of our computations, we make use of inference algorithms from Bayesian networks and encoding techniques from constraint reasoning. We discuss the algebraic theory underlying our framework and point out several generalizations which are possible thanks to the use of semiring theory.

Introduction

Attack-defense trees [START_REF] Kordy | Foundations of Attack-Defense Trees[END_REF] extend the well-known model of attack trees [START_REF] Schneier | Attack Trees[END_REF], by considering not only actions of an attacker, but also possible countermeasures of a defender. Since the augmented formalism models interactions between an attacker and a defender explicitly and is able to capture evolutionary aspects of attack-defense scenarios, it allows for a more accurate security assessment process compared to attack trees. In [START_REF] Kordy | Computational Aspects of Attack-Defense Trees[END_REF], we have proven that the analysis of attack-defense trees is computationally not more expensive than the analysis of attack trees. Furthermore, the usefulness of attack-defense trees for the analysis of real-world security problems has been validated in a large industrial case study [START_REF] Bagnato | Attribute Decoration of Attack-Defense Trees[END_REF]. These results show that attack-defense trees have the potential to become an efficient and practical security modeling and risk assessment tool.

Quantifying probabilistic aspects of attacks is one of the most important issues in security evaluation. Decisions concerning which defensive mechanisms should be implemented are based on the success probability of potential attacks. Furthermore, estimation of probability is necessary in order to evaluate risk related measures. Hence, a fully fledged methodology for security analysis needs to contain a mature framework for probabilistic computations. Unfortunately, the standard bottom-up approach for quantitative analysis of attack

The original publication is available at: http://www.springer.com/ tree-based formalisms [START_REF] Mauw | Foundations of Attack Trees[END_REF][START_REF] Kordy | Attack-Defense Trees[END_REF] can only be used for computing probabilities under the assumption that all considered actions are independent. This is a very strong assumption which is unrealistic for real-life situations.

In this paper, we develop a complete framework for probability computations on attack-defense trees. Our approach combines the security methodology of attack-defense trees with the probabilistic framework of Bayesian networks. This allows us to overcome the mentioned limitation of the bottom-up approach and perform probabilistic computations in the presence of dependent actions. Since attack trees are formally a subclass of attack-defense trees, our framework applies directly for the analysis of the former model. Thus, the paper also contributes to the development of full-fledged analysis technique for attack trees which are widely accepted and commonly used by industry [START_REF] Kordy | DAG-Based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees[END_REF].

We give a brief overview of the attack-defense tree methodology in Section 2. After recalling basic concepts for Bayesian networks, we present our framework for dependent probability computations on attack-defense trees, in Section 3. Sections 4 and 5 are concerned with methods for improving the efficiency of the framework. We describe related work in Section 6 and conclude in Section 7.

Modeling of Security Scenarios

This section provides background knowledge about attack-defense trees, which is necessary to understand the framework developed in this paper. For a more detailed description of the formalism, we refer to [START_REF] Kordy | Attack-Defense Trees[END_REF] and [START_REF] Kordy | Computational Aspects of Attack-Defense Trees[END_REF].

Attack-Defense Trees

Attack-defense trees (ADTrees) allow to illustrate and quantify security scenarios that involve two opposing players: an attacker and a defender. The root of an ADTree represents the main goal of one of the players. When the root is an attack node, the tree represents how to attack a considered system. Conversely, when the root is a defense node, the tree is concerned with defending the system. In ADTrees, both types of nodes, attacks and defenses, can be conjunctively or disjunctively refined. A goal represented by a conjunctively refined node is reached when all the subgoals depicted by its child nodes are reached. A goal represented by a disjunctively refined node is reached when at least one of the subgoals depicted by its child nodes is reached. The refinement operation is applied until basic actions are obtained. Actions are considered to be basic if they can be easily understood and quantified. Basic actions are represented by the nodes which do not have any children of the same type. Each node of an ADTree can also have one child of the opposite type. Children of the opposite type represent countermeasures. These countermeasures can be refined and countered again. In ADTrees, attack nodes are modeled by circles, defense nodes by rectangles. A conjunctive refinement is depicted with an arc. Countermeasures are connected to the actions they counteract by a dotted line. Example 1. Consider a scenario in which an attacker wants to infect a computer with a virus. In order to do this, the attacker needs to ensure that the virus file is accessible from the targeted computer and that it is executed. There are two possibilities to make the file accessible: an attacker can send the virus in an e-mail attachment or distribute an infected USB stick to the computer user. The computer user, on his part, can protect himself against a virus with an anti-virus program. For the anti-virus to be effective, it needs to be installed and it needs to be running. A resourceful attacker, in turn, could attack the anti-virus by using a fake version of an anti-virus, that disables the real anti-virus from running and only pretends that it is running. Fig. 1 depicts the described attack-defense scenario using an ADTree. In this tree, the basic actions are:

For the attacker

For the defender SE -"Send E-mail with Attachment"

IA -"Install Anti-virus" DU -"Distribute USB Stick" RA -"Run Anti-virus" SA -"Spoof Anti-virus" EV -"Execute Virus"

The attack-defense scenario described above is used as the running example in this paper. Its main role is to illustrate how the introduced methodology works. We purposely keep the example simple (and incomplete) in order not to overwhelm the reader with too complex models. Remark 1. Since the root of the ADTree in Fig. 1 represents an attack goal, the paper is concerned with the probability of attacking a system. In the case of an ADTree having a defensive root node, we would talk about the probability of defending a system.

The Propositional Semantics for ADTrees

In order to provide a broad spectrum of analysis methods, several formal semantics for ADTees have been defined in [START_REF] Kordy | Attack-Defense Trees[END_REF]. In this paper, we employ the propositional semantics which makes use of Boolean functions.

By r, we denote a countable set of propositional variables. A configuration with finite domain u ⊆ r is a function x : u → {0, 1} that associates a value x(X) ∈ {0, 1} with every variable X ∈ u. Thus, a configuration x ∈ {0, 1} u represents an assignment of Boolean values to the variables in u.

Definition 1. A Boolean function f with domain u is a function f : {0, 1} u → {0, 1} that assigns a value f (x) ∈ {0, 1} to each configuration x ∈ {0, 1} u .
Given a configuration x with domain u ⊆ r, we denote by x ↓w the projection of x to a subset w ⊆ u. Let f and g be two Boolean functions with domains u and w, respectively. The disjunction (f ∨ g) and the conjunction (f ∧ g) of f and g are Boolean functions with domain u ∪ w, defined for every x ∈ {0, 1} u∪w by:

(f ∨ g)(x) = max{f (x ↓u ), g(x ↓w )}, (f ∧ g)(x) = f (x ↓u ) × g(x ↓w ).
The negation of f (denoted by ¬f ) is a Boolean function with domain u, defined for every x ∈ {0, 1} u by: (¬f )(x) = 1 -f (x). Now, we explain how the propositional semantics associates ADTrees with Boolean functions. Let B denote the set of all basic actions. First, for every B ∈ B, a propositional variable X B ∈ r is constructed. We assume that for B, B ∈ B, B = B =⇒ X B = X B . Next, a Boolean function f t is associated with every ADTree t, as follows.

-If t = B ∈ B, then f B : {0, 1} {X B } → {0, 1} is defined as f B (X B ) = X B .
In other words, the Boolean function associated with B is an identity function. Thus, we often abuse notation and use

X B instead of f B . -If t is disjunctively refined into t 1 , . . . t k , then 1 f t = k i=1 f ti , -If t is conjunctively refined into t 1 , . . . t k , then f t = k i=1 f ti , 1
Here, and stand for extensions of conjunction and disjunction of two Boolean functions to any finite number of Boolean functions. They are well-defined by associativity of × and max.

-If t is countered, then f t = f t1 ∧ ¬f t2 , where t 1 corresponds to the refining subtree and t 2 represents the countering subtree.

Example 2. Applying the introduced recursive construction results in the following Boolean function for the ADTree t from Figure 1:

f t = (X SE ∨ X DU ) ∧ ¬(X IA ∧ (X RA ∧ ¬X SA )) ∧ X EV . (1)
Given an ADTree t, we denote by var t the domain of the Boolean function f t . In other words, var t is the set of propositional variables corresponding to the basic actions involved in t. A configuration x ∈ {0, 1} vart represents which actions succeed (the corresponding variables are set to 1) and which do not (the corresponding variables are set to 0). Following our terminology convention from Remark 1, if f t (x) = 1, then we say that x is an attack with respect to t.

Probabilistic Evaluation of ADTrees

The most often used computational procedure for quantitative assessment of ADTrees relies on a bottom-up procedure [START_REF] Schneier | Attack Trees[END_REF][START_REF] Mauw | Foundations of Attack Trees[END_REF][START_REF] Kordy | Attack-Defense Trees[END_REF][START_REF] Kordy | Quantitative Questions on Attack-Defense Trees[END_REF]. In this approach, values are assigned to the basic actions and the bottom-up algorithm is used to determine the values of the remaining nodes as a function of the values of their children. The computation stops when the value for the root node has been found. Since the value of a node only depends on the values of its children, and not on their meaning, the bottom-up procedure cannot take dependencies between actions into account. Thus, this technique implicitly assumes that all actions of an ADTree are independent. In the case of the probability parameter, such an assumption is unrealistic. For instance, the probability that the defender runs an anti-virus program depends on whether the anti-virus is installed or not.

In order to compute the probability of attacking a system, while taking dependencies between involved actions into account, we propose a framework which combines attack-defense trees with Bayesian networks.

Bayesian Network Associated with an ADTree

A Bayesian network [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] is a graphical representation of a joint probability distribution over a finite set of variables with finite domains. The network itself is a directed, acyclic graph that reflects the conditional interdependencies between the variables associated with the nodes of the network. A directed edge from the node associated with variable X 1 to the node associated with variable X 2 means that X 2 stochastically depends on X 1 . Each node contains a conditional probability table that quantifies the influence between the variables. The joint probability distribution p of a Bayesian network over {X 1 , . . . , X n } is given by

p(X 1 , . . . , X n ) = n i=1 p(X i | par(X i )), (2)
where, par(X i ) denotes the set of nodes that have an outgoing edge that points into X i . If the set par(X i ) is empty, the conditional probability becomes an ordinary probability distribution. Nodes (or subgraphs) of the Bayesian network that are unconnected represent stochastically independent (sets of) variables.

Our goal is to create a Bayesian network depicting stochastic dependencies between the actions involved in a security scenario given as an ADTree. In the ADTree methodology, refined nodes do not contain any additional information, other than how their children are connected (conjunctively or disjunctively). This means that refined nodes do not depict any additional actions. This is why, when constructing a Bayesian network for an ADTree, we take only basic actions into account.

A Bayesian network associated with an ADTree t, denoted by BN t , is a Bayesian network over the set of propositional variables var t , such that there exists a directed edge from X A to X B if and only if action B stochastically depends on action A. Bayesian network BN t complements ADTree t with additional information which is not contained in t. The structure of the Bayesian network BN t is usually constructed manually. This process can however be supported by numerous existing approaches for constructing Bayesian networks [START_REF] Van Harmelen | Handbook of Knowledge Representation[END_REF].

Example 3. A Bayesian network BN t associated with our running ADTree t is shown in Fig. 2. The joint probability distribution for BN t is

p(X EV , X SE , X DU , X SA , X RA , X IA ) = p(X RA |X IA ) × p(X IA )× (3) p(X EV |X SE , X DU ) × p(X SE |X SA ) × p(X DU |X SA ) × p(X SA ).
Install Anti-virus Run Anti-virus p(XIA = 1) = 0.6 p(XRA = 1|XIA = 1) = 0.9 p(XRA = 1|XIA = 0) = 0.0 The conditional probability tables used in Figure 2 have been constructed on an intuitive basis. The accuracy of the input values, as well as the actual methods for their estimation are a research topic in itself and are outside the scope of this submission. In the rest of the paper, we assume that the conditional probability tables have been constructed and are available.

Send E-mail with Attachment Execute Virus Spoof Anti-virus Distribute USB Stick p(XDU = 1|XSA = 1) = 0.4 p(XDU = 1|XSA = 0) = 0.5 p(XEV = 1|XSE = 1, XDU = 1) = 0.9 p(XEV = 1|XSE = 1, XDU = 0) = 0.2 p(XEV = 1|XSE = 0, XDU = 1) = 0.8 p(XEV = 1|XSE = 0, XDU = 0) = 0.1 p(XSE = 1|XSA = 1) = 0.9 p(XSE = 1|XSA = 0) = 0.5 p(XSA = 1) = 0.3

Probabilistic Computations in the Presence of Dependencies

We now present our framework for probability computations on an ADTree t, taking the dependencies between the involved actions into account. Our computation makes use of the Boolean function f t and the Bayesian network BN t .

Given configuration x ∈ {0, 1} vart , we define

ψ t (x) = f t (x) × p(x), ( 4
)
where p is the joint probability distribution of BN t . If x is an attack with respect to t, then f t (x) = 1 and ψ t (x) returns the probability value for x from the Bayesian network, representing the success probability of attack x. If x is not an attack with respect to t, then f t (x) = 0 and thus ψ t (x) = 0.

Example 4. Consider the situation where the attacker installs a virus file on the system by sending an e-mail with attachment (X SE = 1 and X DU = 0), executes the virus file (X EV = 1), but does not use a fake anti-virus program (X SA = 0). The defender, in turn, installs a real anti-virus (X IA = 1) which however is not running (X RA = 0). The corresponding configuration

x = (X EV = 1, X SE = 1, X DU = 0, X SA = 0, X RA = 0, X IA = 1)
is an attack, because

f t (x) (1) = (X SE ∨ X DU ) ∧ ¬(X IA ∧ (X RA ∧ ¬X SA )) ∧ X EV (x) = 1.
By instantiating formula (3) with values from Fig. 2, we obtain that this attack will be successfully executed with the probability

ψ t (x) = f t (x) × p(x) = p(X EV = 1|X SE = 1, X DU = 0) × p(X SE = 1|X SA = 0) ×p(X DU = 0|X SA = 0) × p(X SA = 0) × p(X RA = 0|X IA = 1) × p(X IA = 1) = 0.2 × 0.5 × (1 -0.5) × (1 -0.3) × (1 -0.9) × 0.6 = 0.0021.
Next, assume we are not interested in calculating the probability of successfully executing a specific set of basic actions, but more generally in the success probability of attacking a system according to the scenario represented with ADTree t. This corresponds to the sum of the probabilities of all possible attacks with respect to t. We thus have

P (t) = x∈{0,1} var t ψ t (x) (4) = x∈{0,1} var t f t (x) × p(x).
(

) 5
We refer to the value P (t) as the probability related to ADTree t. Finally, the success probability of the most probable attack with respect to t is computed as

P max (t) = max x∈{0,1} var t ψ t (x) (4)
= max

x∈{0,1} var t f t (x) × p(x). (6)

ADTrees as Constraint Systems

We know that the number of possible configurations is exponential with respect to the number of basic actions. Thus, for large systems, the brute force computation of P (t) and P max (t), as suggested by formulae ( 5) and ( 6), is no longer possible. We now present methods allowing us to represent P (t) and P max (t) in a factorized form, in order to increase the efficiency of their computations.

Indicator Functions for ADTrees

We

φ(Y, Y 1 , Y 2 ) = 1 if Y = Y 1 × (1 -Y 2 )
f t = (X SE ∨ X DU ) Y1 ∧¬ (X IA ∧ (X RA ∧ ¬X SA ) Y2 ) Y3 Y4
∧X EV

Yt

In this case, the inner variables are Y 1 , Y 2 , Y 3 , Y 4 , Y t and the local indicators are

φ 1 (Y 1 , X SE , X DU ) = 1 exactly if Y 1 = max(X SE , X DU ), φ 2 (Y 2 , X RA , X SA ) = 1 exactly if Y 2 = X RA × (1 -X SA ), φ 3 (Y 3 , X IA , Y 2 ) = 1 exactly if Y 3 = X IA × Y 2 , φ 4 (Y 4 , Y 1 , Y 3 ) = 1 exactly if Y 4 = Y 1 × (1 -Y 3 ), φ 5 (Y t , Y 4 , X EV ) = 1 exactly if Y t = Y 4 × X EV .
Let t be an ADTree. Having constructed all local indicators, we can build the global indicator function φ t . The domain of φ t contains all variables used by the local indicators, i.e., the inner variables and the variables corresponding to basic actions of t. An assignment over all variables is valid if and only if each local assignment is valid. Hence, we may compute the global indicator function for f t by multiplying all its local indicators. For the function from Example 5, we get:

φ t (Y 1 , Y 2 , Y 3 , Y 4 , Y t , X SE , X DU , X RA , X SA , X IA , X EV ) = φ 1 (Y 1 , X SE , X DU )× φ 2 (Y 2 , X RA , X SA ) × φ 3 (Y 3 , X IA , Y 2 ) × φ 4 (Y 4 , Y 1 , Y 3 ) × φ 5 (Y t , Y 4 , X EV ). (7)
In this paper, we use the following notation: given the global indicator function φ t for t, we denote by Y t the inner variable corresponding to the entire tree t. The set of all inner variables of φ t is denoted by d t .

Consider an indicator function φ(Y, Y 1 , . . . , Y k ). Let z be an assignment of values to the variables Y 1 , . . . , Y k . There is, by definition, exactly one value y ∈ {0, 1} for Y , such that φ(y, z) = 1. Since the global indicator function is obtained by multiplication, we may directly conclude the following theorem.

Theorem 1. Consider an ADTree t with basic actions B 1 , . . . , B n and its global indicator function φ t . Given a specific assignment x of values to the variables X B1 , . . . , X Bn corresponding to basic actions, there is exactly one assignment y to the inner variables from d t , such that φ t (y, x) = 1.

An immediate consequence of Theorem 1 is that, for a specific assignment x ∈ {0, 1} vart of values to the variables associated with basic actions, we have

max y∈{0,1} d t φ t (y, x) = y∈{0,1} d t φ t (y, x) = 1. (8)
When performing probabilistic computations as specified by formulae (4), ( 5) and ( 6), we are only interested in those combinations of basic actions that correspond to attacks. Thus, when reasoning in terms of global indicator functions, we need to restrict our considerations to those configurations where variable Y t equals 1. This can be achieved by conditioning φ t on Y t = 1, which means that we invalidate all configurations with Y t = 0. We therefore define a filter F t for the ADTree t that satisfies F t (Y t ) = 1 if and only if Y t = 1. In other words, F t : {0, 1} {Yt} → {0, 1} is the identity function for variable Y t . Multiplying filter F t and global indicator φ t results in a function, denoted by φ t|Y t=1 , which maps to 1 if and only if the assignment of values to the variables is valid with respect to f t and it represents an attack according to t. We thus have,

∀z ∈ {0, 1} vart ∪dt : φ t|Y t=1 (z) = F t (z ↓{Yt} ) × φ t (z). (9)
Let t be an ADTree, φ t be its global indicator function and F t be the filter for t. Assume furthermore that we are given a specific configuration x ∈ {0, 1} vart . Configuration x is an attack with respect to t if and only if, there exists y ∈ {0, 1} dt , such that φ t|Y t=1 (y, x) maps to 1. Using formula [START_REF] Van Harmelen | Handbook of Knowledge Representation[END_REF], we obtain

max y∈{0,1} d t φ t|Y t=1 (y, x) = y∈{0,1} d t φ t|Y t=1 (y, x) = f t (x) = 1 if x is an attack 0 otherwise. ( 10
)

Indicators for Probability Computation

Making use of the property described by [START_REF] Kohlas | Semiring induced Valuation Algebras: Exact and Approximate Local Computation algorithms[END_REF], the procedure for the probabilistic computations developed in Section 3.2 can be redefined as follows. Let t be an ADTree and x ∈ {0, 1} vart be an assignment of Boolean values to the variables corresponding to the basic actions of t. If x is an attack with respect to t, then its probability is computed as

ψ t (x) (4)
= f t (x) × p(x) (10), distrib. = y∈{0,1} d t φ t|Y t=1 (y, x) × p(x) (11)
(10), distrib. = max y∈{0,1} d t φ t|Y t=1 (y, x) × p(x) . (12)
The probability related to ADTree t is expressed as

P (t) (5) = x∈{0,1} var t ψ t (x) (11) = x∈{0,1} var t y∈{0,1} d t φ t|Y t=1 (y, x) × p(x) = z∈{0,1} var t ∪d t φ t|Y t=1 (z) × p(z ↓vart ) . ( 13
)
Similarly, the probability of the most probable attack with respect to t is

P max (t) (6) = max x∈{0,1} var t ψ t (x) (12)
= max z∈{0,1} var t ∪d t

φ t|Y t=1 (z) × p(z ↓vart ) . ( 14
) Example 6. Let u = {Y 1 , Y 2 , Y 3 , Y 4 , Y t , X SE , X DU , X RA , X SA , X IA , X EV }.
The factorized form for the probability related the ADTree from Figure 1 is

P (t) (13)
,( 9),( 7),( 3)

= (15) z∈{0,1} u F t (z ↓{Yt} ) × φ 1 (z ↓{Y1,XSE,XDU} ) × φ 2 (z ↓{Y2,XRA,XSA} ) × φ 3 (z ↓{Y3,XIA,Y2} ) × φ 4 (z ↓{Y4,Y1,Y3} ) × φ 5 (z ↓{Yt,Y4,XEV} ) × p(z ↓{XEV,XSE,XDU} ) × p(z ↓{XSE,XSA} ) × p(z ↓{XDU,XSA} ) × p(z ↓{XSA} ) × p(z ↓{XRA,XIA} ) × p(z ↓{XIA} ) .
The factorization of the global indicator function, in terms of local indicators which are bounded in size, introduces additional structure that can be exploited for so-called local computation [START_REF] Pouly | Generic Inference -A Unifying Theory for Automated Reasoning[END_REF]. In this section, we show how the fusion algorithm allows us to improve the efficiency of evaluating formulas ( 13) and ( 14).

Semiring Valuations

An algebraic structure A, ⊕, with binary operations ⊕ and is called commutative semiring if both operations are associative, commutative, and if distributes over ⊕, i.e., if for a, b, c ∈ A, we have a

(b ⊕ c) = (a b) ⊕ (a c) and (a ⊕ b) c = (a c) ⊕ (b c).
Typical examples of commutative semirings include the Boolean semiring {0, 1}, max, × , the tropical semiring N, min, + , the product t-norm semiring [0, 1], max, × and the arithmetic semiring R, +, × .

Let u ⊆ r be a finite set of propositional variables and A, ⊕, be a commutative semiring. A semiring valuation over A, ⊕, is a function φ : {0, 1} u → A associating a value from A with each configuration from {0, 1} u . We denote by dom(φ) = u the domain of valuation φ. The combination of two valuations φ and ψ over a semiring A, ⊕, is defined, for all x ∈ {0, 1} dom(φ)∪dom(ψ) , as:

(φ ⊗ ψ)(x) = φ(x ↓dom(φ) ) ψ(x ↓dom(ψ) ).
The elimination of variable X ∈ dom(φ) is defined, for all x ∈ {0, 1} dom(φ)\{X} , as:

φ -X (x) = φ(x, 0) ⊕ φ(x, 1).
Due to associativity of semiring addition ⊕, we can eliminate variables in any order. For {X 1 , . . . , X m } ⊆ dom(φ), we may therefore write φ -{X1,...,Xm} = . . . (φ -X1 ) -X2 . . .

-Xm

.

Indicator functions are Boolean semiring valuations over {0, 1}, max, × . Arithmetic semiring valuations over R, +, × capture conditional probability tables from Bayesian networks, and product t-norm semiring valuations over [0, 1], max, × compute maximum attack probabilities, as in formula [START_REF] Kordy | Quantitative Questions on Attack-Defense Trees[END_REF]. It has been shown in [START_REF] Kohlas | Semiring induced Valuation Algebras: Exact and Approximate Local Computation algorithms[END_REF] that semiring valuations over arbitrary commutative semirings always satisfy the axioms of a valuation algebra [START_REF] Kohlas | Information Algebras: Generic Structures for Inference[END_REF][START_REF] Pouly | Generic Inference -A Unifying Theory for Automated Reasoning[END_REF]. The computational interest in valuation algebras is stated by the inference problem. Given a set of (semiring) valuations {φ 1 , . . . , φ n }, called knowledgebase, with domains u i = dom(φ i ), for i = 1, . . . , n, and a set of variables {X 1 , . . . , X m } ⊆ u 1 ∪. . .∪u n , the inference problem consists of computing φ -{X1,...,Xm} = (φ 1 ⊗ . . . ⊗ φ n ) -{X1,...,Xm} .

(

) Example 7. Let u = {Y 1 , Y 2 , Y 3 , Y 4 , Y t , X SE , X DU , X RA , X SA , X IA , X EV }. 16
Computing the probability in Example 6 amounts to solving the inference problem

F t (z ↓{Yt} ) × φ 1 (z ↓{Y1,XSE,XDU} ) × . . . × p(z ↓{XIA} ) -u = z∈{0,1} u F t (z ↓{Yt} ) × φ 1 (z ↓{Y1,XSE,XDU} ) × . . . × p(z ↓{XIA} ) .
Here, the knowledgebase consists of all local indicator functions, filter F t and all conditional probability tables, which instantiate arithmetic semiring valuations. Likewise, computing maximum attack probability, expressed by formula ( 14), amounts to solving a similar inference problem over the product t-norm semiring.

Fusion

A direct evaluation of formulas ( 13), ( 14), and more generally of ( 16), is in most cases not possible, due to the exponential complexity of combination of semiring valuations. However, because the computational tasks are stated with respect to a factorization of the global indicator function and the joint probability distribution, we may exploit the additional structure inside the factorization and perform calculations locally on the domain of the factors. Fusion [START_REF] Shenoy | Valuation-Based Systems: A Framework for Managing Uncertainty in Expert Systems[END_REF] (or bucketelimination [START_REF] Dechter | Bucket Elimination: A Unifying Framework for Reasoning[END_REF]) is one of the local computation algorithms that can be applied to factorizations of arbitrary valuation algebras. Thus, we may use it for processing inference problems obtained from ADTrees. The elimination of a single variable X ∈ dom(φ) = dom(φ 1 ) ∪ . . . ∪ dom(φ n ) from a set {φ 1 , . . . , φ n } of valuations can be performed as follows:

Fus X ({φ 1 , . . . , φ n }) = {ψ -X } ∪ {φ i : X / ∈ dom(φ i )}, (17)
where ψ = i : X∈dom(φi) φ i . This means that we only need to eliminate X from the factors that have X in the domain. As described in [START_REF] Kohlas | Information Algebras: Generic Structures for Inference[END_REF], the fusion algorithm then follows by repeated application of this operation:

(φ 1 ⊗ . . . ⊗ φ n ) -{X1,...,Xm} = Fus Xm (. . . (Fus X1 ({φ 1 , . . . , φ n }))).
In every step i = 1, . . . , m of the fusion algorithm, the combination in ( 17) creates an intermediate factor ψ i with domain dom(ψ i ). Then, variable X i is eliminated only from ψ i in [START_REF] Lagerström | Extended Influence Diagram Generation[END_REF]. We define λ(i) = dom(ψ i ) \ {X i } called label and observe that λ(m) = (dom(φ 1 ) ∪ . . . ∪ dom(φ n )) \ {X 1 , . . . , X m }. The domains of all intermediate results of the fusion algorithm are therefore bounded by the size of the largest label plus one. The smaller the labels are, the more efficient fusion is. We further remark that the labels depend on the chosen elimination sequence for variables X 1 , . . . , X m . Finding a sequence that leads to the smallest label is NP-complete [START_REF] Arnborg | Complexity of Finding Embeddings in a k-Tree[END_REF], however, there are good heuristics that achieve reasonable execution time [START_REF] Dechter | Constraint Processing[END_REF]. In summary, the complexity of computing ( 16) is not necessarily exponential in the number of variables involved in the problem, but only in the size of the largest label, also called tree width [START_REF] Robertson | Graph Minors I: Excluding a Forest[END_REF], that occurs during fusion.

We have applied fusion to the inference problem from Example 7. The results show that, when fusion is used, time and space complexity of the computation of P (t) for our running ADTree are bounded by 2 5 . To compare, a naive, direct computation, as in [START_REF] Kordy | DAG-Based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees[END_REF], is bounded by 2 11 . We have also automated the computation of P (t) with the help of the open-source tool Nenok [START_REF] Pouly | NENOK -A Software Architecture for Generic Inference[END_REF] which provides an extensive library of generically implemented local computation algorithms. When applying fusion, Nenok outputs the value of P (t) after 0.031 sec in contrast to 3.422 sec that the application requires to compute the same value in a naive way, i.e., by using expression (15) directly.

Related Work

ADTrees are only one of more than 30 graphical formalisms for security assessment, which are based on attack trees. A recent survey, by Kordy et al. [START_REF] Kordy | DAG-Based Attack and Defense Modeling: Don't Miss the Forest for the Attack Trees[END_REF] presents a complete state of the art in the field of DAG-based approaches for modeling of attacks and defenses. It summarizes existing formalisms, compares their features and proposes their taxonomy. The reader is referred to this survey for an overview of existing methods for quantitative, and in particular probabilistic, analysis of security. In the remainder of this section, we compare our framework with the most prominent, existing models that combine AND-OR graphs with Bayesian networks.

Qin and Lee are one of the pioneers in applying Bayesian networks for security analysis [START_REF] Qin | Attack plan recognition and prediction using causal networks[END_REF]. They propose a conversion of regular attack trees into Bayesian networks, in order to make use of probabilistic inference techniques to evaluate the likelihood of attack goals and predict potential upcoming attacks. Edges representing disjunctive refinements in the tree are also present in the corresponding Bayesian network, because they represent cause-consequence relations between components. Contrary to our interpretation, a conjunction in attack trees is assumed to have an explicit or implicit order in which the actions have to be executed. This allows to convert conjunctions into a directed path in the Bayesian network, starting from the first child, according to the given order, and ending with the parent node. The construction from [START_REF] Qin | Attack plan recognition and prediction using causal networks[END_REF] implies that the Bayesian network and the attack tree contain the same set of nodes. Furthermore the Bayesian network models cause-consequence relationships that correspond to the child-parent connections in the underlying attack tree. In our case, the Bayesian network depicts additional dependencies that represent how different basic actions are influenced by each other.

In [START_REF] Frigault | Measuring Network Security Using Bayesian Network-Based Attack Graphs[END_REF], Frigault and Wang advance a model, called Bayesian attack graphs. They construct a Bayesian network starting from an attack graph which depicts how multiple vulnerabilities may be combined in an attack. The resulting directed acyclic graph contains all nodes of the original attack graph. Employing the CVSS mechanism [START_REF] Mell | A Complete Guide to the Common Vulnerability Scoring System Version 2[END_REF], the nodes are then associated with the conditional probability tables. In [START_REF] Poolsappasit | Dynamic Security Risk Management Using Bayesian Attack Graphs[END_REF], Poolsappasit et al. revisit the framework of Bayesian attack graphs to be able to deal with asset identification, system vulnerability and connectivity analysis, as well as mitigation strategies. In addition to the con-ditional probability tables that represent the probability with which an attack takes place, they consider edge probabilities expressing how likely a present attack succeeds. Furthermore, the authors of [START_REF] Poolsappasit | Dynamic Security Risk Management Using Bayesian Attack Graphs[END_REF] augment Bayesian attack graphs with additional nodes and values representing defenses. This extended structure allows them to solve the multiobjective optimization problem of how to select optimal defenses. Even though this model is similar to ours, it does not cover interleaved attacks and defenses.

Yet another approach that makes use of Bayesian networks for security analysis was described by Sommestad et al. [START_REF] Sommestad | Modeling security of power communication systems using defense graphs and influence diagrams[END_REF]. It transforms defense trees [START_REF] Bistarelli | Defense Trees for Economic Evaluation of Security Investments[END_REF] (an extension of attack trees with defenses attached to leaf nodes) into extended influence diagrams [START_REF] Lagerström | Extended Influence Diagram Generation[END_REF] (an extension of Bayesian networks with conjunctive and disjunctive nodes as well as countermeasures). The relationships between the nodes are encoded in conditional probability tables assigned to each node. The authors state that with this setup, Bayesian inference can be used to derive values, however they do not provide detailed computation algorithms. Our paper specifies how the necessary computational steps could be performed.

Contrary to our design, none of the above approaches separate the logical structure (conjunctions and disjunctions) from the probabilistic structure. One advantage of our approach is that we are not transforming one model into another, but we are using them modularly. Merging the two methodologies is only implicitly done during fusion. Unlike our model, all related approaches assume a one-to-one correspondence between the nodes in the original graph and the Bayesian network. Since in our framework, the Bayesian network concerns only basic actions, its size is much smaller compared to the size of Bayesian networks used by the approaches described in this section.

Conclusion and Future Work

This paper proposes to combine the ADTree methodology with Bayesian networks in order to evaluate probabilistic measures on attack-defense scenarios involving dependent actions. The introduced approach improves upon the standard, bottom-up, computational routine for attack tree-based formalisms, which assumes that all actions involved in the model are independent. By lifting the independency assumption, we provide a pragmatic methodology for accurate probabilistic assessment of security scenarios modeled using attack trees or ADTrees.

In our framework, the Bayesian network does not replace the information represented by the structure of an ADTree, but complements it with additional probabilistic dependencies between attack steps, which cannot be depicted using AND-OR relations. Keeping the two models separated allows us to take advantage of the strengths of both formalisms. The propositional encoding of ADTrees is used to identify configurations which represent attacks. Bayesian networks together with the fusion algorithm and techniques based on semiring valuation algebras provide ways to improve the efficiency of probabilistic computations.

To support modeling and quantitative analysis of security using the ADTree methodology, a free software tool, called ADTool [START_REF] Kordy | ADTool: Security Analysis with Attack-Defense Trees[END_REF], has recently been devel-oped. We are currently extending the functionality of ADTool by interfacing it with Nenok, so that it can handle the framework introduced in this paper. Since Nenok implements generic algorithms for efficient processing of semiring-based computations, the extended tool will support efficient, automated probabilistic analysis of real-world, possibly large-scale, attack-defense scenarios.

Employing fusion implies that time and space complexity are bounded by a structural parameter of the problem rather than by the total number of variables involved. It thus cannot be predicted in general how well fusion can cope with large problems involving many variables. It all depends on whether a small tree width (or good elimination sequence) can be found by some heuristic. Prediction of the tree width is possible for specific families of graphs [START_REF] Bodlaender | A Partial K-arboretum of Graphs with Bounded Treewidth[END_REF]. It is one of our future research directions to investigate whether combination of an ADTree with a Bayesian network, both produced by human security experts, would satisfy the definition of one such family.

The algorithmic technique based on semiring valuations that we have used in this paper also works in a broader context. From an algebraic perspective, the combination of indicator functions and probabilities is possible because the Boolean semiring for indicator functions is a sub-algebra of both semirings used for expressing probabilities, i.e., the arithmetic and product t-norm semiring. Consequently, we may directly apply the same construction to other semiring valuations under the additional condition that the corresponding semiring takes the Boolean semiring as sub-algebra. The large family of t-norm semirings [START_REF] Pouly | Generic Inference -A Unifying Theory for Automated Reasoning[END_REF] are important candidates used in possibility and fuzzy set theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF].

Fig. 1 .

 1 Fig. 1. ADTree for infecting a computer.

Fig. 2 .

 2 Fig. 2. Bayesian network BNt associated with ADTree t from Figure 1.

  and 0 otherwise. Example 5. A step-wise construction of the local indicators for the Boolean function given in Example 2 proceeds as follows:

  If f t = f t1 ∧¬f t2 , then the propositional variables Y , Y 1 and Y 2 are associated with f t , f t1 and f t2 , respectively, and the local indicator function for f t is defined as:

employ an encoding technique from constraint reasoning and construct a factorized indicator function φ t for the Boolean function f t . Indicator φ t maps to 1 if and only if its arguments represent a valid assignment with respect to f t . The construction of the global indicator φ t relies on local indicators that make use of inner variables and are defined as follows. 1. If f t = k i=1 f ti , then the propositional variables Y, Y 1 , . . . , Y k are associated with f t , f t1 , . . . , f t k , respectively, and the local indicator function for f t is defined as: φ(Y, Y 1 , . . . , Y k ) = 1 if Y = max{Y 1 , . . . , Y k } and 0 otherwise. 2. If f t = k i=1 f ti , then the propositional variables Y, Y 1 , . . . , Y k are associated with f t , f t1 , . . . , f t k , respectively, and the local indicator function for f t is defined as: φ(Y, Y 1 , . . . , Y k ) = 1 if Y = Y 1 × . . . × Y k and 0 otherwise. 3.

Acknowledgments. We would like to thank Sjouke Mauw, Pieter Hartel, Jan-Willem Bullée, Lorena Montoya Morales, and the anonymous reviewers for their valuable comments that helped us to improve the paper. The research leading to these results has received funding from the European Union Seventh Framework Programme under grant agreement number 318003 (TREsPASS) and from the Fonds National de la Recherche Luxembourg under grants PHD-09-167 and C13/IS/5809105.