Magali Magnin
email: magali.magnin@cea.fr

Sophie Schuller

Daniel Caurant

Odile Majérus

Dominique De Ligny

T Advocat

Phase separation and crystallization in soda-lime borosilicate glass enriched in MoO3

à 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

In order to confine the high level wastes (HLW) such as fission product solutions, arising from reprocessing of high burn-up UOX-type nuclear spent fuels, a new glass composition is being optimized [1]. The studies conducted to date on this borosilicate glass revealed that above about for more than 3 wt%, molybdenum oxide can lead (for glasses fabricated at 1200°C), to a glass-in-glass phase separation, followed by crystallization upon cooling. Concerning the structural role of molybdenum in silicate and borosilicate glasses, X-ray absorption spectroscopy showed that hexavalent molybdenum cations are located in unconnected tetrahedral MoO 4 2-entities within alkali and alkaline-earth rich depolymerised regions outside the silicate or borosilicate network (i.e., the oxygen atoms of MoO 4 2-units are not bounded to Si or B) [2][3][4][5]. The same kind of isolated molybdate tetrahedral entities are present in the Na 2 MoO 4 and CaMoO 4 phases that can form in some nuclear borosilicate glasses. On account of the solubility of alkali molybdates in water, this phase separation may decrease the chemical durability of the vitrified nuclear waste material [6]. The similarity between the local environment of MoO 4 2-entities in glasses and in molybdate crystalline phases may explain the low solubility of molybdenum in glasses and their tendency to crystallize during slow cooling of melts or heat treatment of glasses.

The present work was performed to identify the different steps of the transformation from the melt to the glass of a borosilicate glass rich in MoO 3 with Raman spectroscopy in temperature. A composition containing 2mol.% MoO 3 was chosen because depending on the type of cooling applied it allows to obtain an homogenous or partially crystallized glass.

EXPERIMENTAL PROCEDURE

Glass Preparation

For this study, a non-radioactive simplified glass composition was chosen in the SiO 2 -B 2 O 3 -Na 2 O-CaO system derived from that of a HLW glass keeping the same oxides ratio as in this complex composition. Two glass compositions (Table I) were prepared for this study: one with 2mol.% of MoO 3 (M2) and another without MoO 3 (M0). For all samples, 0.15 mol.% Nd 2 O 3 was introduced to facilitate 29 Si and 95 Mo nuclei relaxation during MAS NMR experiments and to perform optical studies not presented in this paper. Various cooling scenarios were tested for each composition: quenching between two copper plates (speed cooling about 10 4 °C/min), cooling on metallic plate (speed cooling about 10 3 °C/min). Moreover, M2 glass was also cooled by air blowing according to the method described by Schuller et al [7]: the sample were taken directly in the platinum crucible at 1100°C using a ring-tipped platinum rod then blown with compressed air through a nozzle. After blowing the samples were very thin films of glass about 10 µm thick formed by bursting of glass bubbles, and constitute the very fast-quenched specimens. This method of cooling permitted to quench the molten glass at higher temperature than the two other methods (with a speed cooling higher than 10 4 °C/min).

Samples Characterization

M2 samples quenched between copper plates or cooled on metallic plate were characterized by XRD on a Philips X'Pert Pro theta-theta X-ray diffractometer using monochromatised Cu Kα radiation (λ = 0.15406 nm). Crystalline phases were identified by comparison of XRD powder patterns with the crystallographic data base of the International Center of Diffraction data. The M2 sample cooled on metallic plate (opalescent) was studied by SEM and energy dispersive X-ray analysis (EDX). Very fast-quenched M2 samples prepared by air blowing or quenched between two copper plates were analyzed by TEM and EDX.

In order to establish the phase separation and crystallisation sequence occurring during the cooling, the Raman spectra of the M2 glass quenched between two copper plates were recorded in the temperature range 1100-25°C (after melting again at 1100°C).

Raman spectra of crystalline phases Na 2 MoO 4 (commercial sample) and CaMoO 4 (ceramic sample prepared in our laboratory) was also recorded in the same range of temperature for comparison with our partially crystallized samples and for temperature calibration. For this Raman experiment, an Aramis Jobin-Yvon confocal microRaman spectrometer equipped with a CCD detector was used. The 325 nm line of a Coherent He-Cd laser was the excitation source. High-temperature Raman observations were carried out in a Linkam T1500 heated stage for the collection of in-situ Raman spectra. Samples were put into the Pt crucible of heated stage and directly melted at 1100°C. Then, samples were cooled at the rate of 100°C/min. All Raman spectra were corrected for temperature and frequency-dependent scattering intensity as described by Long [START_REF] Long | Raman Spectroscopy[END_REF] and then normalized to the data point of highest intensity.

RESULTS

Microstructural Characterization of M2 glass quenched at different rates

As shown in Fig. 1, the M2 glasses obtained after quenching between two copper plates or blowing by air were transparent and totally amorphous according to XRD and TEM. However, the M2 sample cooled on metallic plate glass was opalescent and the back-scattered SEM image showed white spherical micrometer size particles homogeneously dispersed in the bulk (Fig. 1c). XRD pattern of this sample revealed the presence of CaMoO 4 (powellite) and γ-Na 2 MoO 4 crystals (Fig. 1e). Powellite has the same tetragonal structure as scheelite (CaWO 4 ) with nearly regular isolated MoO 4 2-tetrahedra and one site for Ca 2+ ions in which these cations are surrounded by eight close oxygen atoms. According to literature [START_REF] Petrosyan | [END_REF]10], γ-Na 2 MoO 4 is an orthorhombic phase stable only at high temperature (between 592 and 637°C) [10]. The apparent spherical shape of the Mo-rich particles tends to indicate that molybdate crystallized in spherical shape particles previously formed by liquid-liquid phase separation in the melt during cooling. These liquid spherical particles would concentrate Mo and would then facilitate molybdate crystallization [11].

Study of M2 Glass During Cooling

In order to determine the appearance temperature of phase separation and crystallization phenomenon, the M2 glass obtained after quenching between two copper plates was selected and studied by Raman spectroscopy in temperature during the cooling (from 1100°C to room temperature). For each temperature, the Raman spectra of M2 sample were compared with those of molybdate crystalline phases (CaMoO 4 and Na 2 MoO 4 ) recorded separately in the same temperature range. For this high temperature study, Raman spectra were recorded from 100 to 1200cm -1 . Consequently, the principal vibration bands (internal modes) of MoO 4

2-entities which are in crystallized (as CaMoO 4 or Na 2 MoO 4 ) or in amorphous environment were observed.

From 1100°C To 950°C

The image (Fig. 1a) of M2 sample cooled by air blowing from 1100°C showed that this glass was homogeneous at the TEM scale (no crystalline phase was detected). It is supposed that molybdenum is totally located inside the glassy network at this temperature. The Raman spectrum of M2 sample (melt) recorded at 1100°C (Fig. 2a) reveals the presence of a main band at 901 cm -1 . The Raman spectrum (recorded at room temperature) of the glass M0 without molybdenum (Fig. 2b) shows that this band is not present without molybdenum. Thus, this band may be associated with a vibration band of MoO 4 2-entities in a glassy environment. The fact that the Raman spectrum of glass M2 could not be correlated with the spectrum of crystalline CaMoO 4 whose main band is narrower and is located at 885 cm -1 (T = 1100°C) confirms that molybdenum is not located in molybdate crystals. According to Sarantopoulou et al [12] the band at 885 cm -1 is associated to the symmetric stretching vibration band of MoO 4 2-entities in the crystalline phase CaMoO 4 at 1100 ° C. Upon cooling from 1000 to 950°C there are not modifications of the vibration band associated with the elongation of MoO 4 2-entities. Thus it appears that in this temperature range, tetrahedral MoO 4

2-entities are only located in a glassy environment. The absence of stretching vibration bands characteristics of MoO 4 2-inside crystallized environment indicates that the melt is not crystallized in the temperature range from 1100 to 950°C.

From 950°C to room temperature

Below 950°C, a strong evolution of the bands associated with MoO 4 2-entities vibration is observed. Indeed, the Raman spectrum of M2 sample recorded at 900°C shows now a main vibration band at 867 cm -1 (Fig. 3a). This wave number is associated with vibration bands of tetrahedral MoO 4

2-entities in a crystallized environment of CaMoO 4 type. The new band at 780cm -1 (Fig. 3a) also corresponds to a vibration band of tetrahedral MoO 4 2-entities in CaMoO 4 crystals. Moreover a weak shoulder is observed near 900 cm -1 which is characteristic of the MoO 4 2vibration band in the glass as shown in Fig. 2a. This shoulder appears in all Raman spectra recorded for each temperature. Between 800 and 700°C, Raman spectra of M2 (Fig. 3b,c) remained similar; the elongation vibration band of MoO 4 2-tetrahedra in CaMoO 4 is always observed. Starting from 650°C, a low-intensity shoulder appeared at 890 cm -1 in the M2 Raman spectrum (Fig. 3d). The intensity of this shoulder increased in the Raman spectrum recorded at 550°C (Fig. 3e). When comparing this spectrum with that of Na 2 MoO 4 recorded at the same temperature, we can see that this band may be associated with a vibration band of tetrahedral MoO

4 Fig. 1 .

 41 Fig. 1. TEM images of M2 samples cooled by blowing air at 1100°C (a) or quenched between two copper plates (b). Back-scattered electron (SEM) image of M2 sample cooled on metallic plate (c). X-ray diffraction (XRD) patterns of the quenched glasses between two copper plates (d) or cooled on metallic plate (e).

Fig. 2 .Fig. 3 .

 23 Fig. 2. (a) . Normalized Raman spectra of M2 sample (melt) recorded at 1100°C. Raman spectra of CaMoO 4 crystalline phase at the same temperature also shown for comparison. (b) Normalized Raman spectra of M0 glass recorded at room temperature.

TABLE I

 I

	. Nominal Glass Compositions (oxide
	mol.%).
		M0	M2
	% SiO 2	66.40	65.07
	% B 2 O 3	10.75	10.54
	% Na 2 O	14.05	13.76
	% CaO	8.65	8.48
	% Nd 2 O 3	0.15	0.15
	% MoO 3	0	2.00
	All glasses (~ 50 g batch) were prepared using
	reagent grade SiO 2 , CaCO 3 , Na 2 CO 3 , H 3 BO 3 ,
	MoO 3 , and Nd 2 O 3 powders and melted under air
	in platinum/gold crucibles at 1300°C for 3 h.

May 19-22, 2008

DISCUSSION

The TEM image of M2 sample quenched by air blowing from 1100°C argues that the melt is homogeneous at this temperature. The Raman spectrum recorded at 1100°C confirms that the tetrahedral MoO 4 2-entities are in a glassy environment (absence of crystallization). During melt cooling of M2 sample from 1100°C to 950°C, there is no evolution of Raman spectra. However, the microstructure of M2 cooled on metallic plate suggests that the phenomenon of phase separation appears before crystallization. Therefore, it is expected to observe the liquidliquid phase separation phenomenon in this temperature range. The first CaMoO 4 crystals appear between 950 and 900°C, and this crystalline phase remains up to room temperature. Between 700 and 650°C, two low-intensity shoulders appear which can be correlated with stretching elongation bands of MoO 4 2-entities in the crystalline phase Na 2 MoO 4 type and in the glass. The probable scenario of the different phenomenon occurring during M2 melt cooling deduced from all our results is reported in Fig. 4.

CONCLUSIONS

The aim of this work was to study a glass belonging to the SiO 2 -B 2 O 3 -Na 2 O-CaO system rich in MoO 3 . The glass quickly cooled at 10 4 °C/min is homogenous. But when it is cooled more slowly (about 10 3 °C/min) CaMoO 4 and Na 2 MoO 4 crystallization occurs in the bulk. By Raman spectroscopy investigations from the melt temperature (1100°C) to room temperature, CaMoO 4 crystallization occurs near 900°C while the Na 2 MoO 4 crystallization appears at lowertemperature (near 650°C). Thus we identified the occurrence temperatures of crystalline phase CaMoO 4 and Na 2 MoO 4 in borosilicate glass rich in MoO 3 during slow cooling. In order to quantify the thermal stability areas of these crystalline phases, a study on glass heating is under progress. Further studies will be carried out in order to determine the appearance temperature of the phase separation phenomenon, and to describe the microstructural evolution of glass M2. In addition, the composition effects will be studied with the aim of increasing the solubility of MoO 3 in borosilicate glasses.


Frederic Cuppens
email: cuppens@cert.fr

Alban Gabillon
email: gabillon@univ-tln.fr

Cover Story Management

Keywords: Database Security, Security Model, Multilevel Security Policy, Cover Story Management, Mathematical Logic

In a multilevel database, cover stories are usually managed using the ambiguous technique of polyinstantiation. In this paper, we define a new technique to manage cover stories and propose a formal representation of a multilevel database containing cover stories. Our model aims to be a generic model, that is, it can be interpreted for any kind of database (e.g. relational, objectoriented etc). We then consider the problem of updating a multilevel database containing cover stories managed with our technique.

Introduction

The work presented in this paper applies to the context of multilevel security policies. In a multilevel security policy every piece of information is associated with a classification level, and every agent is associated with a clearance level. Classification and clearance levels are taken from a set of security levels. This set is partially ordered and forms a lattice. The partial ordering relation is called the dominance relation and is denoted by ≥. The confidentiality property in the multilevel security policy states that an agent can only know a given piece of information if the clearance level of this agent dominates (that is, is higher than or equal to) the classification level associated with the piece of information.

Currently, database security is an active field of research. Several theoretical models have been suggested for multilevel databases (see, for instance, [DLSSH88,KTT89,HOST90,JK90, Lun90,SW92,ML92,QL96, SC98,JVPJ99]). Most of these models offer the possibility to insert cover stories in the multilevel database. Cover stories are lies introduced in the multilevel database in order to protect some existing higher classified data. In most of these models, cover stories are associated with the concept of polyinstantiation. Polyinstantiation occurs when different tuples with the same key, each at a different classification level, are allowed. Low level tuples are then interpreted as cover stories. Unfortunately, the concept of polyinstantiation is not satisfactory since it is not free of semantic ambiguities. decided to focus on cover stories, therefore we have not mentioned this possibility (see [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF] for the semantics of this special "Restricted" value).

The remainder of this paper is organized as follows. Section 2 introduces, in an informal way, the concept of cover story and outlines the problems related to polyinstantiation. Section 3 proposes a model for a multilevel database containing cover stories. Section 4 describes how cover stories can be practically managed and how the consistency and the security property of the database can be maintained after an update has occurred. Section 5 concludes this paper.

Cover Stories and Polyinstantiation

We shall use the following two lattices throughout the paper:

U_S:

{(U)nclassified,(S)ecret} with S > U U_C1_C2_S: {(U)nclassified,(C 1 )onfidential1,(C 2 )onfidential2,(S)ecret} with S>C 1 , S>C 2 , C 1 >U, C 2 >U and C 1 <>C 2 (which means C 1 and C 2 are not comparable)

Intuitively, a cover story is a lie inserted in a multilevel database in order to hide the existence of a sensitive data.

Let us use U_S and let us consider a multilevel database containing the following fact:

Salary (Dupont,2000) which reads "Dupont's salary is 2000"

Let us assume this fact is classified at the Secret level:

[Salary( Dupont,2000)] S which reads "the fact that Dupont's salary is 2000 is Secret"

Let us assume an Unclassified user u queries the database and asks "What is Dupont's salary?". Obviously, the database cannot answer "Dupont's salary is 2000" since this is a Secret fact. Let us assume that the database answers "You are not allowed to know this data". From this answer, u deduces that the salary of Dupont is Secret1 . In other words, u deduces the following sentence:

∃x,[Salary(Dupont,x)] S which reads "there exists a Secret salary for Dupont" However, the Security Administrator (SA) might consider this sentence to be itself Secret that is:

[∃x,[Salary(Dupont,x)] S ] S which reads "the fact that there exists a Secret salary for Dupont, is itself Secret" In this case, the database cannot answer "You are not allowed to know this data"2 . As a solution the SA may insert a salary at the Unclassified level in the multilevel database.

[Salary(Dupont,1500)] U Now, there are two salaries for Dupont in our multilevel database: one Unclassified, 1500 and one Secret, 2000. In the literature, the salary of Dupont is referred to as a polyinstantiated set of two classified values.

Polyinstantiation was first used in the SeaView project [START_REF] Denning | The Sea View Security Model[END_REF]. With this technique different tuples may have the same primary key provided each of them has a different classification level. Low-classified tuples are implicitly interpreted as cover stories.

Therefore, according to polyinstantiation, 1500 is interpreted as a cover story that is, a lie which is used to hide from Unclassified users the existence of a more sensitive salary for Dupont. 2000 is interpreted as the Dupont's real salary. If u asks "What is Dupont's salary?" then the database answers "Dupont's salary is 1500". Therefore, u cannot deduce the existence of a more sensitive salary. If a Secret user expresses the same query then the database answers "Dupont's salary is 2000" and possibly informs the Secret user about the existence of a cover story at the Unclassified level.

Despite the broad use of polyinstantiation by the community working on multilevel databases, we claim that this technique is not appropriate to cover story management. Our aim, now, is to describe some of the problems which are related to the use of polyinstantiation.

Ambiguous interpretation of data

Let us consider our previous multilevel database containing the following two classified facts:

[Salary(Dupont,1500)] U [Salary(Dupont,2000)] S
With the polyinstantiation technique, 1500 is interpreted as a cover story whereas 2000 is interpreted as the Dupont's real salary. This interpretation implicitly suggests that there exists an integrity constraint stating that the salary of Dupont is unique. However, if the database does not contain such an integrity constraint then this database could also represent the fact that Dupont has two salaries: one Unclassified, 1500, and one Secret, 2000. In this latter case a Secret user querying the database and asking "What is Dupont's salary?" should be answered as "2000 and 1500" and not as "2000" only.

Poor expressive power of the security policy

Polyinstantiation allows us to introduce cover stories which are "attribute values" only (e.g. the salary attribute of the entity Dupont). It does not provide us with any means to introduce an "entity" cover story. For example, we cannot introduce a lie saying that another person, Durand, is an employee.

Polyinstantiation does not work in case of a partial order on the set of security levels

Let us use U_C1_C2_S and let us consider a multilevel database containing the following two classified facts:

C Salary

Let us assume we have an integrity constraint saying that Dupont's salary is unique. At least, one of these two salaries is then a lie. However, polyinstantiation does not provide us with any means to know which of these two salaries is a cover story.

In the remaining of this paper, our objective is to define a new technique for managing cover stories. We show that our technique is free of semantic ambiguities and it offers a security policy with a great expressive power.

Multilevel database

Classified facts and integrity constraints

Mathematical logic has often been used to formalize databases. In [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF] we define a complete logical theory which represents a multilevel database. In this paper, in order not to repeat what was written in [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF] and to highlight our new cover story management technique, we shall only mention the relevant characteristics of our model without going into formal details.

We consider that a multilevel database DB contains a set F of classified atomic facts and a set IC of classified integrity constraints.

For the sake of simplicity we also assume that integrity constraints are all classified at the lowest level U.

Example:

Let us use U_S.

F = { [Employee(Dupont)] U
which reads " Dupont is an employee". This fact is U.

[Salary(Dupont,2000)] S } which reads "Dupont'salary is 2000". This fact is S.

IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U (1)
which reads "Anybody who has a salary is an employee". This constraint is U.

[ ∀x, Employee(x) → ∃y,Salary(x, y) ] U (2) which reads "each employee has a salary". This constraint is U.

Formulae of IC F ∪ are axioms of our logical theory.

We also extend our theory with the following axiom schema (p denotes an atomic fact or an integrity constraint. l denotes a security level):

[ ] [ ] l l l l p p l l l l ′ = → ′ ≤ ∧ ∧ ′ ∀ ∀ ′ , (3)
This axiom schema says that a fact or an integrity constraint cannot be associated with two distinct comparable security levels. This means that if p is classified with two levels l and l' and if l' dominates l then l and l' are the same. This axiom implicitly suggests that p may be associated with more than one security level provided these security levels cannot be compared between each other:

Example :

Let us use U_C1_C2_S.

According to axiom schema (3), [ ] [ ] 1 ) Dupont ( Dupont) ( C U Employee Employee ∧ is not possible since C 1 >U whereas [ ] [ ] 2 1 ) Dupont ( ) Dupont ( C C Employee Employee ∧ is possible since 2 1 C C <> .

Cover Stories

A multilevel database may contain lies, which are cover stories. We have seen in section 2 that polyinstantiation is often suggested as a solution to manage cover stories. However, we have also seen in section 2 that there are several problems related to the use of polyinstantiation. Therefore, the aim of this section is to propose a new technique to manage cover stories.

F = { [Employee(Durand)] U [Salary(Durand,1000)] U }
In this example the fact that Durand is an employee is a lie. On the contrary, the fact that Durand receives a salary of 1000 is not a lie ! One can reasonably guess that the information "Durand is an employee" has been introduced at the Unclassified level in order to justify the fact that Durand receives a salary. This example shows that we can create "entity" cover stories.

Note that this database is not consistent with integrity constraint (1). Indeed, Secret users see a salary for Durand but Durand is not an employee. This contradicts integrity constraint (1). Consequently, the above example is possible if, either IC does not contain integrity constraint (1) or, CS IC contains a fact saying that integrity constraint (1) is a cover story:

IC = { [ ∀x,
F = { 1 )] Dupont ( [ C Employee 2 )] Dupont ( [ C Employee 1 )] 1500 , Dupont ( [ C Salary 2 )] 2000 , Dupont ( [ C Salary }
Secret users are explicitly informed that 1500 at the C 1 level is a cover story. Our technique allows us to manage cover stories even if we have a partial order on the set of security levels.

These three examples have given us an overview of the expressive power of a security policy which would manage cover stories using our technique.

Definition of a multilevel database

We define the multilevel database DB as follows:

IC F CS CS IC F DB ∪ ∪ ∪ =
Formulae belonging to DB are axioms of our logical theory.

Axiom schemata specifying the links between the cover stories and the other data are the following (p is either a fact or an integrity constraints):

[ ] [ ] l CS l p l l l p l ′ ∧ < ′ ′ ∃ → ∀ , , (4)
Axiom (4) says that if the fact that p is a cover story is classified at level l then there exists a level l' strictly dominated by l such that p is classified at level l'.

Note that from axioms (4) and (3) we can derive the following theorem:

[ ] [ ] l CS l p p l ¬ → ∀ , (5)
Theorem (5) says that if the fact that p is a cover story is classified at level l then p cannot be classified at level l.

Proof:

Let us assume that [ ] CS l p l, ∃ From (4) we can derive that [ ] l l p l l < ′ ∧ ′ ∃ ′ , Axiom (3) can be rewritten as [ ] [ ] l l p l l p l l ¬ → < ′ ∧ ′ ∀ ∀ ′ , Therefore, we can derive that [ ] l p ¬
Derivation in the multilevel database is based on the classical Modus Ponens inference rule (that is, if p is a theorem and if "p implies q" is a theorem then we can derive that q is also a theorem). We write p DBwhich reads p is derived from DB.

We do not use the closed world assumption since the closed world assumption generally leads to inconsistency when it is combined with disjunctions. Negative facts can be either derived from some of the axioms given previously (see for instance the theorem 5) or from axioms of completion (see [START_REF] Reiter | Toward a logical reconstruction of relational database theory[END_REF]). We did not explicitly mentioned these axioms in the previous examples but they should be considered as implicit. For instance, sets F and CS F of example 1 should be rewritten as follows:

F = { [ ] [ ] U U x x Employee x Dupont ) ( , = ↔ ∀ [ ] [ ] U U y x y x Salary y x 1500 Dupont ) , ( , = ∧ = ↔ ∀ ∀ [ ] [ ] S S y x y x Salary y x 2000 Dupont ) , ( , = ∧ = ↔ ∀ ∀ } CS F = { [ ] [ ] S CS S y x y x Salary y x 1500 Dupont ) , ( , = ∧ = ↔ ∀ ∀ }

Definition of a consistent multilevel database

A multilevel database represents a part of the real world. Facts and integrity constraints which belong to the multilevel database, and which are not cover stories, exist also in the world represented by the multilevel database. This can be expressed by the following sentence:

[ ] [ ] p p l l l p l CS l l → ∧ < ∃ ¬ ∧ ∀ ′ ) ' , ' ( , (6)
Formula (6) says that if p is classified at level l and if p is not declared as a cover story in the upper levels then p is not a lie, that is, p exists in the real world.

Using formula (6), we can easily derive the world represented by the multilevel database. From

CS F = { [ ] CS S Salary ) 1500 , Dupont ( [ ] CS S Employee ) Durand ( } F = { [Employee(Dupont)] U [Salary(Dupont,1500)] U [Salary(Dupont,2000)] S [Employee(Durand)] U [Salary(Durand,1000)] U } CS IC = { [ ] CS S x Employee y x Salary y x ) ( ) , ( , → ∀ ∀ } IC = { [ ∀x∀y, Salary(x, y) → Employee( x)] U [ ∀ x, Employee(x) → ∃ y,Salary(x, y) ] U }
The world represented by this multilevel database is the following:

F Real = { Employee(Dupont)
Salary (Dupont,2000) Salary(Durand,1000) }

IC Real = { ∀x, Employee(x) → ∃y,Salary(x, y) }
We say that a multilevel database

IC F CS CS IC F DB ∪ ∪ ∪ =
is consistent if and only if:

1. { } 4 , 3 - ∪ ∪ ∪ IC F CS CS IC F
which reads "axiom schemas (3) and (4) can be derived from DB".

2.

Real Real IC F which reads "integrity constraints of IC Real can be derived from the set of facts F Real " One can easily see that our previous example of multilevel database is consistent.

Definition of a secure multilevel database

A multilevel database might be consistent but not free of illegal inference channels. There is an illegal inference channel when a low level user can deduce some sensitive information from the low classified data.

Example 5:

Let us use U_S and let us consider the following multilevel database:

CS F = {} F = { [Employee(Dupont)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U }
The world represented by this database is the following:

F Real = { Employee(Dupont) Salary(Dupont,2000)} IC Real = { ∀x, Employee(x) → ∃y,Salary(x, y)
∀x∀y,Salary(x, y) → Employee( x)}

One can easily see that this database is consistent. However, it is not free from illegal inference channels. Indeed, Unclassified users can see both the Unclassified fact Employee(Dupont) and the Unclassified integrity constraint ∀x, Employee(x) → ∃y,Salary(x, y) . By assuming that the database is consistent, these users can learn that Dupont has a salary and that his salary is Secret.

Let DB l be the view of the multilevel database at level l. DB l contains all the data (facts, integrity constraints and cover stories) which are classified at a level lower than or equal to l.

IC l F l l l l CS CS IC F DB ∪ ∪ ∪ = Let Real l Real l IC F
∪ be the world which can be derived from DB l .

We say that a consistent database DB l is secure (or respects the confidentiality property) if and only if for all security level l' (with l ≥ l'), DB l' is consistent, that is for all security level l', we have:

1. { } 4 , 3 - ∪ ∪ ∪ ′ ′ ′ ′ IC l F l l l CS CS IC F 2. Real l Real l IC F ′ ′ -
Note that, saying that DB is secure is equivalent to say that DB high is secure since DB = DB high . high is the security level dominating all the other security levels (recall that the set of security levels forms a lattice).

Our previous multilevel database is not secure because DB U is not consistent:

F U CS = {} F U = { [Employee(Dupont)] U } IC U CS = {} IC U = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U }
The world represented by DB U is the following:

Real U F = { Employee(Dupont) } Real U IC = { ∀x, Employee(x) → ∃y,Salary(x, y) ∀x∀y,Salary(x, y) → Employee( x)}
We see that

Real U Real U IC F -/ . In particular ) , ( , ) ( , y x Salary y x Employee x F Real U ∃ → ∀ -/ .
Note that in [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF], we state two inference rules which allow us to derive some inference control theorems from the integrity constraints. In [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF], we say that a multilevel database is secure if it respects these theorems. The definition used in this paper is more general. Indeed, in [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF] we make some assumptions on the form of integrity constraints we may insert in the database. In particular, we assume we cannot have disjunctive integrity constraints such as:

) ( ) ( ) ( , x Woman x Man x Human x ∨ → ∀
which reads "every human being is either a man or a woman".

In this paper we do not make any restrictive assumption on the form of integrity constraints.

We could show that if a database is secure regarding the definition given in [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF] then it is also secure regarding the definition given in this paper.

Note also that "DB being secure" means only that the integrity constraints cannot be used to derive protected data. Of course, a low level user might still be able to deduce some high classified data from an external knowledge not represented in the database.

The aim of the next section is to investigate the problem of updating a multilevel database containing cover stories which are handled with our technique.

Updating a multilevel database

Single-level Transactions

Let DB be a secure multilevel database. We assume DB can be updated through single-level transactions only. Before starting a single-level transaction, a user must first choose a transaction level l. This transaction level l must be dominated by the clearance level of the user. Then, the user may read data at a level dominated by l and may insert/update/delete data at a level equal to l, this, in accordance with the No-Read-Up and No-Write-Down principles of the Bell & LaPadula model [START_REF] Bell | Secure Computer Systems: Unified Exposition and Multics Interpretation[END_REF].

We assume there is no restriction on the data the user may access within the transaction. This means that a user may access data from F, IC, CS F , CS IC .

We say that the commitment of a transaction of level l is accepted if DB l is secure. It is rejected otherwise.

This principle seems reasonable. A transaction of level l being rejected means that DB l is not secure. Since a user of level l is allowed to see the whole DB l database, rejecting the transaction does not violate the confidentiality property.

On the other hand, if DB l is secure then the transaction must be accepted and committed, even if the whole DB database is not secure. Indeed rejecting the transaction in case DB l is secure and DB not secure would open a covert channel. 1.

Let T be an Unclassified transaction inserting in F the new fact Employee(Durand). T is rejected since the new DB U would not be consistent. Indeed there would be a new employee Durand without a salary in

Real U

F . This would contradict the integrity constraint ∀x, Employee(x) → ∃y,Salary(x, y) belonging to Real U IC . Therefore DB is not updated.

2.

Let T be an Unclassified transaction updating the fact [Salary(Dupont,1500)] U into the fact [Salary(Dupont,1600)] U . T is accepted and committed since the new DB U is consistent. DB becomes the following:

CS F = { [ ] CS S Salary ) 1500 , Dupont ( } F = { [Employee(Dupont)] U [Salary(Dupont,1600)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U }
We can easily see that DB U is consistent. However, we also see that DB is not consistent (in particular, we see that DB is not consistent with axiom (4). Indeed, there is a fact at level S saying that Salary(Dupont,1500) is a cover story whereas it does no longer appear in the unclassified database Consequently, the main question is, what should be done in such a case to make the whole DB secure again ?

There are several possible answers to this question. We are going to deal with them in the next section of this paper. However, the following preliminary action must be taken in any case:

If DB is not secure after a transaction has been committed, then a mechanism alerting the Security Administrator (SA) must be triggered.

Of course this mechanism must be triggered through a trusted path and must not be seen by low level users.

Restoring the security property -Basic algorithm

Let us consider a secure database DB. Let us assume DB is updated by a transaction T. T is committed. Let us assume the new DB is not secure.

According to the principle enounced in the previous section, a mechanism informing the SA has been triggered. The SA may then take any decision that he estimates the best to restore the security property of DB. However, the SA is a human being. He cannot react instantly. Consequently, during a certain period of time, DB remains in an non-secure state. This may be unacceptable.

The solution to cope with this problem is to let the DBMS take a decision and restore immediately the confidentiality property of DB. Of course, the SA might later reverse the operations performed by the DBMS and perform other operations if necessary.

We suggest that the DBMS applies the following algorithm in order to restore the confidentiality property of DB:

1.

If DB is not consistent with axiom (3) that is, there exists a fact or a constraint p associated with two comparable security levels l and l' with l < l', then [p] l' is deleted.

[p] l' is deleted since p is disclosed at a level strictly lower than l'.

2.

If DB is not consistent with axiom (4) that is, there exists a l-classified data saying that a fact or a constraint p is a cover story and there is no security level l' (with l' < l) protecting p,

then [ ] CS l p is deleted.
[ ] CS l p is deleted since p is not contained in the database at any level strictly lower than l.

3.

Let I = { p 1 , p 2 , … , p n }. Each p i is either a fact belonging to F or an integrity constraints belonging to IC.

I is inconsistent if and only if the integrity constraints belonging to I cannot be derived from the facts belonging to I.

I is minimal inconsistent if and only if I is inconsistent and every strict subset of I is consistent.

Let us consider the following rule to restore the database consistency:

If I = { p 1 , p 2 , … , p n } is a minimal inconsistent set and if we have [ ] [ ] ) , , lub( 1 1 1 n l n l l l l p p n K K = ∧ ∧ ∧ 3 , then we have: [ ] [ ] CS l n CS l p p ∨ ∨ K 1
This means, at least one of the p i is a cover story and the fact that it is a cover story is classified at level l.

We call this rule the cs-rule.

Using this cs-rule the DBMS must attempt to derive some new cover stories. This algorithm is a general algorithm which may be refined. Step 3 of this algorithm says that if I is a minimal inconsistent set then one of the p i is a cover story. Recall that each p i is either a fact or an integrity constraint. Recall also that step 3 of the algorithm is used by the DBMS to derive some new cover stories. Knowing this, we could decide that the DBMS should trust the integrity constraints more than the facts. Therefore, we could refine the algorithm with the following step 4: This means that the DBMS should consider that integrity constraints belonging to I cannot be cover stories.

In the remainder of this paper we shall assume that step 4 is part of the algorithm.

In many cases, our algorithm will enable the DBMS to restore the security property of DB. However, in some cases (see example 10 below), the DBMS will only succeed in deriving a sentence

like [ ] [ ] CS l k CS l p p ∨ ∨ K 1
from DB and will not be able to determine which of the p i is a cover story. If this occurs, then a solution might be to accept that DB remains in a non-secure state until the SA intervenes. Before the SA restores the security property of DB, the DBMS must provide l-level or higher-level users with the

sentence [ ] [ ] CS l k CS l p p ∨ ∨ K 1
, that is, the DBMS must inform these users that DB is not secure and that one of the p i is a cover story. However, avoiding a situation where the DBMS fails in restoring the security property of DB is possible, but it requires some complementary mechanisms or principles which are suggested in section 4.2.

Let us consider the following examples:

Example 7:

3 Lub = least upper bound Let us use U_S and let us consider the database DB represented in the example 1 of page 6. The following constraint is added to the set IC of integrity constraint:

[ y y y x Salary y x Salary y y x ′ = → ′ ∧ ′ ∀ ∀ ∀ ) , ( ) , ( , ] U (7)
(which reads "the salary is unique". This constraint is Unclassified)

Let T be an Unclassified transaction updating the fact [ Salary(Dupont,1500)] U into the fact [Salary(Dupont,1600)] U . T is accepted and committed since the new DB U is consistent. As a result, the database becomes the following:

CS F = { [ ] CS S Dupont Salary ) 1500 , ( }
F = { [Employee(Dupont)] U [Salary(Dupont,1600)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U [ y y y x Salary y x Salary y y x ′ = → ′ ∧ ′ ∀ ∀ ∀ ) , ( ) , ( , ] U }
DB is not consistent. The DBMS must attempt to restore the security property of DB: Let us use U_S and let us consider the database DB represented in the example 1 of page 6. This database is the same as the initial database defined in the previous example. The only difference is that constraint (7) has been removed. Let us consider the same transaction T executed at level U which updates the fact [ Salary(Dupont,1500)] U into the fact [ Salary(Dupont,1600)] U . T is accepted and committed since the new DB U is consistent. Then the database becomes the following: Then DB becomes the following: The database becomes the following:

CS F = { [ ] CS S Dupont Salary ) 1500 , ( }
F = { [Employee(Dupont)] U [Salary(Dupont,
CS F = {} F = { [Employee(Dupont)] U [Salary(Dupont,1600)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U } DB is
CS F = { [ ] CS S Dupont Salary ) 1500 , ( } F = { [Employee(Dupont)] U [Salary(Dupont,2000)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y, Salary(x, y) → Employee( x)] U [ ∀ x, Employee(x) → ∃ y,Salary(x, y) ] U }
DB is not consistent. The DBMS must attempt to restore the confidentiality property of DB:

• According to step 1 of our algorithm the DBMS deletes [Salary(Dupont,2000)] S .

• According to step 2 of our algorithm the DBMS deletes [ ] CS S Dupont Salary ) 1500 , ( .

Then DB becomes the following:

CS F = {} F = { [Employee(Dupont)] U [Salary(Dupont,2000)] U } CS IC = {} IC = { [ ∀ x ∀ y, Salary(x, y) → Employee( x)] U [ ∀ x, Employee(x) → ∃ y,Salary(x, y) ] U }
DB is now secure. We see that the DBMS has actually downgraded the value 2000. We claim that this is the most appropriate response to the insertion of the value 2000 at the level U, regardless of who initiated the transaction T:

• Let us assume that the user who initiated T is an Unclassified user. Most probably this user updated the value 1500 into the value 2000 because he learned that the real salary of Dupont was 2000. This disclosure means that a violation of the confidentiality property has occurred. Therefore, there is no reason to keep the value 2000 Secret in the database. Of course, the SA who was informed about the update must now investigate and try to discover how the confidentiality property has been violated.

• Let us assume that the user who initiated T is a Secret user operating at the level U. Our interpretation is that this user updated the value 1500 into the value 2000 because he wanted to downgrade the value 2000.

Example 10:

Let us use U_C1_C2_S and let us consider the following database DB:

CS F = { [ ] CS S Dupont Salary ) 1500 , ( } F = { 1 )] Dupont ( [ C Employee 2 )] Dupont ( [ C Employee 1 )] 1500 , Dupont ( [ C Salary 2 )] 2000 , Dupont ( [ C Salary } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U [ y y y x Salary y x Salary y y x ′ = → ′ ∧ ′ ∀ ∀ ∀ ) , ( ) , ( , ] U }
Let us consider a transaction T executed at level C 1 which updates the fact

F C CS 1 = {} 1 C F = { 1 )] Dupont ( [ C Employee 1 )] 1600 , Dupont ( [ C Salary } IC C CS 1 = {} 1 C IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U [ y y y x Salary y x Salary y y x ′ = → ′ ∧ ′ ∀ ∀ ∀ ) , ( ) , ( , ] U } One can easily see that 1 C
DB is secure. T is then accepted and committed. DB becomes the following: DB becomes the following: Solutions to avoid such a situation exist. We briefly present some of them in the next section.

CS F = { [ ] CS S Dupont Salary ) 1500 , ( } F = { 1 )] Dupont ( [ C Employee 2 )] Dupont ( [ C Employee 1 )] , Dupont
CS F = {} F = {

Restoring the security property -Toward an Extended algorithm

The algorithm given in the previous section is a basic algorithm. Example 10 of the previous section has shown us that our algorithm should be extended in order to cope with the situation where the algorithm derives a sentence like [ ] [ ] CS l k CS l p p ∨ ∨ K 1 from the database but cannot determine which of the p i is a cover story. Let us come back to example 10 and let us present some possible extensions for our algorithm.

• The first possibility is to make a non-deterministic choice between the conflicting data. For instance, in example 10, the DBMS can restore the database consistency by nondeterministically deciding that 1600 or 2000 is a cover story. It is the simplest solution and it can apply in every situation. The main drawback is that it is completely arbitrary.

• The SA (or any authorized user) may associate the initial cover story 1500 with a Secret trigger on update. This trigger would automatically insert, through a trusted path, a fact saying that the new updated value at the level C 1 is a cover story.

The database would automatically become as follows: says that Dupont's salary at level C 1 is a cover story. Updating the value 1500 into the value 1600 will not affect the consistency of DB. Consequently, after the update, 1600 will automatically become a cover story.

CS F = { [ ] CS S Salary ) 1600 , Dupont ( } F = { 1 )] Dupont ( [ C Employee 2 )] Dupont ( [ C Employee 1 )] ,
• Finally, [START_REF] Cuppens | Providing Consistent Views in a Polyinstantiated Database[END_REF] suggests that it is often possible to restore the database consistency by making an implicit choice between incomparable security levels. In particular, this implicit choice may be based on need to know requirements and may depend on the type of information to be updated. For instance, regarding the salary, the SA may specify that level C 2 has priority over level C 1 . Therefore, in our previous example, the conclusion would be to consider that 2000 is Dupont's salary and 1600 is a cover story.

However, there are situations where none of the above solutions, except the first one -namely the non-deterministic choice -applies. The following example provides an example of such a situation.

Let us use U_S and let us consider the following database DB:

CS F = {} F = { [Employee(Dupont)] U [Salary(Dupont, 1500
x       ′ ′ = ′ ∨ ′ ′ = ∨ ′ = → ′ ′ ∧ ′ ∧ ′ ′ ∀ ′ ∀ ∀ ∀ ) ( ) ( ) ( ) ,
x       ′ ′ = ′ ∨ ′ ′ = ∨ ′ = → ′ ′ ∧ ′ ∧ ′ ′ ∀ ′ ∀ ∀ ∀ ) ( ) ( ) ( ) , ( ) , ( ) , ( , }
However, DB is not consistent. Indeed, we now have three salaries for Dupont.

In a similar way as we did before, we could show that our algorithm derives the following sentence:

[ ] [ ] CS S CS S Salary Salary ) 1600 , Dupont ( ) 1500 , Dupont ( ∨
that is one of the value 1500 or 1600 is a cover story.

In such a case, in order to restore the consistency of DB, the best solution seems to let the DBMS choose in a non-deterministic way which of the two values is a cover story. For instance the DBMS may choose that 1500 is a cover story. DB becomes then the following: Examples 7 to 9 of section 4.2 have shown us how our basic algorithm may enable the DBMS to maintain the security property of a multilevel database after an update has occurred. However, we have seen through example 10 that this basic algorithm cannot face all situations and must be extended with some complementary principles, some of which have just been presented in this section.

CS F = {

Conclusion

There are situations where it is necessary to insert covert stories in a multilevel database. In section 2, we showed that these situations occur when the security administrator decides to hide the existence of high-classified information from low-classified users. We also showed the limitations of the polyinstantiation technique and suggested a new approach to manage cover stories.

This approach is based on explicit management of cover stories. It enables us to derive a consistent view of the real world for each security level. Moreover, a user cleared at a given security level l is allowed to know all the cover stories having a classification level strictly dominated by l.

As mentioned in section 3.5, this new approach is fully compatible with the one suggested by the authors in [START_REF] Cuppens | Logical Foundations of Multilevel Databases[END_REF]. However, our approach is more general since it does not make any restriction on the form of integrity constraints we may insert in the database.

There are other formal multilevel database security models which do not use the polyinstantiation technique. Smith and Winslett [START_REF] Smith | Entity Modeling in the MLS Relational Model[END_REF] were the first to propose such a model. In their model, a multilevel database is represented by a collection of belief sets associated with each security level. This approach was analyzed and criticized in [START_REF] Cuppens | Querying a Multilevel Database: A Logical Analysis[END_REF]. In particular, it is shown that there is no link between the belief set associated with a given security level l and the belief sets at security levels strictly dominated by l. The conclusion of [START_REF] Cuppens | Querying a Multilevel Database: A Logical Analysis[END_REF] is that [START_REF] Smith | Entity Modeling in the MLS Relational Model[END_REF] is not really a model for a multilevel database but rather a model for a "system-high" database.

Recently, [START_REF] Sandhu | The MLR Data Model[END_REF] and [START_REF] Jukic | A belief-consistent multilevel secure relational data model[END_REF] suggested several improvements to [START_REF] Smith | Entity Modeling in the MLS Relational Model[END_REF]. Links can be created between a database at a given security level l and the ones which are at a level strictly dominated by l. As a matter of fact, a user cleared at a level higher than or equal to l can specify that a fact classified at a level strictly dominated by l is accepted in the database at level l. This is a cautious approach that is efficient to avoid conflicts due to the existence of cover stories at classification levels strictly dominated by l. However, we argue that such a manual management of information flow from low to high classification levels is impractical in real applications.

Therefore, we guess that our approach is more realistic. We suggest an explicit management of cover stories so that any fact whose classification is strictly dominated by l is implicitly (and automatically) accepted at level l as far as it is not declared as a cover story at level l. Moreover, this explicit management makes it possible to eliminate the problems of information choice, for instance in the case of partially ordered set of security levels.

Finally, we have specified rules to control database updates and deletions, especially when a cover story is modified. From a more practical point of view, the data specifying that a given fact is actually a cover story may be stored in specific relations distinct from the ones used to manage the multilevel database. For instance, if R is a multilevel relation, then one can create a relation R CS to store the cover stories associated with relation R. We guess that this overall approach is the most suitable one for future implementations.

  derive F Real , a set of facts existing in the real world, and from IC CS IC ∪ we can derive IC Real , a set of integrity constraints existing in the real world. Example 4: Let us use U_S. Let us consider the following multilevel database:

Example 6 :

 6 Let us use U_S and let us consider the database DB represented in the example 1 of page 6: Let us now consider two examples of Unclassified transactions updating DB:

  if p 1 , p 2 ,…, p k are facts and p k+1 , p k+2 ,…, p n are integrity constraints with 1 ≤ k < n then we have [ ] one of the facts is a cover story.

  1600)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ] U }DB is not consistent. The DBMS must attempt to restore the security property of DB:• According to step 2 of our algorithm the DBMS deletes [ ]

Example 9 :

 9 Let us use U_S and let us consider the database DB represented in the example 1 of page 6: Let us consider a transaction T executed at level U which updates the fact [Salary(Dupont,1500)] U into the fact [Salary(Dupont,2000)] U . T is accepted and committed since the new DB U is consistent.

  [ ∀ x ∀ y, Salary(x, y) → Employee( x)] U[ ∀x, Employee(x) → ∃y,Salary(x, y) ] U DB is not consistent. Until the SA updates the database and restores the consistency of DB, Secret users will be informed that either 1600 or 2000 is a cover story.

  )] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ]

[

  Salary(Dupont,1500)] U [Salary(Dupont,1600)] U [Salary(Dupont,2000)] S } CS IC = {} IC = { [ ∀x∀y,Salary(x, y) → Employee( x)] U [ ∀x, Employee(x) → ∃y,Salary(x, y) ]DB is now secure. 1600 and 2000 are the two Dupont'salaries. 1500 is a cover story.

  The central idea of our technique is to explicitly declare a cover story in either a set CS F (if the cover story is a fact) or in a set CS IC (if the cover story is an integrity constraint).More precisely, if p is a cover story of the multilevel database then we introduce in the multilevel database (in either CS F or CS IC ) a classified data saying that p is a cover story.

	Let us have an overview of our technique through the following three examples:
	Example 1:
	Let us use U_S.
	F = { [Employee(Dupont)] U
	[Salary(Dupont,1500)] U
	[Salary(Dupont,2000)] S }
	IC = { [ ∀x∀y, Salary(x, y) → Employee( x)] U
	[ ∀ x, Employee(x) → ∃ y,Salary(x, y) ] U }
	CS F = { [ Salary	(	Dupont	) 1500 ,	] CS S	}
	(which reads "the fact that the salary of Dupont, 1500, is a cover story, is Secret")
	CS IC = {}
	With our new cover story management technique, 1500 is interpreted as a cover story without any
	ambiguity. If CS F were empty then 1500 would be interpreted as a second salary for Dupont
	without any ambiguity. Since cover stories are explicitly declared, there is no ambiguity in the
	interpretation of the data.
	Example 2:
	Let us use U_S.
	CS F ={ [ Employee	(	Durand	)	] CS S	}

  secure. 1600 is now interpreted as Dupont's second salary. The DBMS could restore the security property of DB.Note that the SA has been informed about the update. Therefore, he may later update DB and insert

	the fact [ Salary	(	Dupont	) 1600 ,	] CS S	if he estimates that 1600 is actually a cover story.

  However the DBMS cannot derive which of the two values is a cover story. The simplest solution is to wait for the intervention of the SA.

	[ ∨ Salary [ x ∀ y ∀ Dupont Salary y ′ ∀ , 2000 x ( ) , ] [ Salary y ∧ ) CS S Salary ( ∨ ( x Dupont y → ′ ) , , 1600 y y = ) ′ ] ] CS S CS S , (
	From step 4 of our algorithm, we derive
	[ Salary	(	Dupont	) 2000 ,	] [ CS S Salary ∨	(	Dupont	) 1600 ,	] CS S
				[	Salary	(							1600	C
				[	Salary	(	Dupont	)] 2000 ,	2 C	}
	CS IC = {}
	IC = {			[ ∀x∀y,Salary(x, y) → Employee( x)] U
				[ ∀x, Employee(x) → ∃y,Salary(x, y) ] U
				[	∀	x ∀	y	y ∀	′ ,	Salary	(	x	,	y	)	∧	Salary	(	x	,	y	′ )	→	y	=	y	′	] U }
	DB is not consistent. The DBMS must attempt to restore the security property of DB:
	• According to step 2 of our algorithm the DBMS deletes [ Salary	(	Dupont	) 1500 ,	] CS S	.
	• According to step 3 and 4 of our algorithm the DBMS derives
	[ Salary	(	Dupont	) 2000 ,	] [ CS S Salary ∨	(	Dupont	) 1600 ,	] CS S
	Proof:
	The set, {Salary(Dupont,1600), Salary(Dupont,2000), y y x Salary y x Salary y y x = → ′ ∧ ′ ∀ ∀ ∀ ) , ( ) , ( ,	y	′	} is minimal inconsistent.
	From [ Salary	(	Dupont	) 2000 ,	] [ 2 C Salary ( ∧	Dupont	) 1600 ,	] C 1	and from the cs-rule defined in
	step 3 of our algorithm, we derive:

  Note that Dupont has two salaries, one Unclassified 1500, and one Secret 2000. Neither of these salaries is a cover story.Let us consider a transaction T executed at level U which inserts the fact [Salary(Dupont,1600)] U . T is accepted and committed since the new DB U is consistent (There are now two salaries at the Unclassified level. This does not violate the integrity constraint which says that nobody can have more than two salaries). The database becomes the following:

	CS IC = {}
	IC = {	[ ∀x∀y,Salary(x, y) → Employee( x)] U
		[ ∀x, Employee(x) → ∃y,Salary(x, y) ] U
		y	y	y	Salary	x	y	Salary	x	y	Salary	x	y
				y	y	y	y	y	y				U
				,	(	,	)	(	,	)	(		}
		which reads "nobody can have more than two salaries"
	CS F = {}
	F = {	[Employee(Dupont)] U
		[Salary(Dupont,1500)] U
		[Salary(Dupont,1600)] U
		[Salary(Dupont,2000)] S }

U_S contains only two security levels {Unclassified, Secret}. If we consider more than two security levels then u would only learn that Dupont'salary is not Unclassified.

Note that, if the SA had considered that the sentence "there exists a Secret salary for Dupont" was Unclassified (that is [∃x,[Salary(Dupont,x)] S ] U ) then the answer "You are not allowed to know this data" would have been acceptable.


František Kardoš
email: frantisek.kardos@upjs.sk.

Daniel Král'

Jan Volec
email: volec@iuuk.mff.cuni.cz.

Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs

We show that for every cubic graph G with sufficiently large girth there exists a probability distribution on edge-cuts in G such that each edge is in a randomly chosen cut with probability at least 0.88672. This implies that G contains an edge-cut of size at least 1.33008n, where n is the number of vertices of G, and has fractional cut covering number at most 1.127752. The lower bound on the size of maximum edge-cut also applies to random cubic graphs. Specifically, a random n-vertex cubic graph a.a.s. contains an edge cut of size 1.33008n.

Introduction

An edge-cut in a graph G = (V, E) defined by X ⊆ V is the set of edges with exactly one end vertex in X (and exactly one end vertex in V \ X).

A maximum edge-cut is an edge-cut with the maximum number of edges. The size of a maximum edge-cut is an important graph parameter intensively studied both in structural and algorithmic graph theory. From the algorithmic point of view, it attracted a lot of attention because of an approximation algorithm based on the semidefinite programming by Goemans and Williamson [START_REF] Goemans | Improved approximation algorithms for maximum cut and satisfability problems using semidefnite programming[END_REF] which achieves the best possible approximation ratio under reasonable computational complexity assumptions [START_REF] Khot | Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?[END_REF]. More specifically, assuming that the Unique Games Conjecture of Koth [START_REF] Khot | On the power of unique 2-prover 1-round games[END_REF] holds, it is NPhard to approximate the size of a maximum edge-cut in a graph G within any factor greater than the approximation factor of the Goemans-Williamson algorithm. On the other hand, there exists a polynomial-time algorithm for finding a maximum edge-cut in planar graphs [START_REF] Hadlock | Finding a Maximum Cut of a Planar Graph in Polynomial Time[END_REF], and more generally in graphs embeddable in a fixed orientable surface [START_REF] Galluccio | Optimization via Enumeration: a new algorithm for the Max Cut Problem[END_REF]. In this paper, we provide new structural results on maximum cuts in cubic graphs, i.e., graphs with all vertices of degree three.

We prove a new lower bound on the size of a maximum edge-cut in a cubic graph with no short cycle and in a random cubic graph. Let us now mention earlier results. In 1990, Zýka [START_REF] Zýka | On the bipartite density of regular graphs with large girth[END_REF] proved that the size of the maximum edgecut in cubic graphs with large girth is at least 9n/7 -o(n) = 1.28571n-o(n). A better bound 1.3056n can be obtained from a recent result [START_REF] Kardoš | Volec: Fractional colorings of cubic graphs with large girth[END_REF] on independent sets in cubic graphs with large girth. The asymptotic lower bound for a maximum edge-cut in random cubic graphs of 1.32595n was given by Díaz, Do, Serna and Wormald [START_REF] Díaz | Bisection of Random Cubic Graphs[END_REF]. The experimental evidence suggests that almost all n-vertex cubic graphs contain an edge-cut of size at least 1.382n [26]. On the other hand, the best known upper bound is 0.9351m = 1.4026n which applies both to random cubic graphs and cubic graphs with large girth. The upper bound was announced by McKay [START_REF] Mckay | Maximum Bipartite Subgraphs of Regular Graphs with Large Grith[END_REF], its rigorous proof can be found in [START_REF] Hladký | Bipartite subgraphs in a random cubic graph[END_REF]. The problem could also be translated to a problem in statistical physics and applying non-rigorous methods suggests that the size of a maximum edge-cut for almost all n-vertex graphs is at most 1.386n [START_REF] Zdeborová | A conjecture on the maximum cut and bisection width in random regular graphs[END_REF].

The problems of determining the size of a maximum edge-cut in random cubic graphs (more generally in random regular graphs) and in cubic (regular) graphs with large girth are closely related. On one hand, Wormald showed in [START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF] that a random cubic graph asymptotically almost surely (a.a.s.) contains only o(n) cycles shorter than a fixed integer g. Therefore, we can a.a.s. remove a small number (which means o(n)) of vertices to obtain a subgraph with large girth and only o(n) vertices of degree less than three.

On the other hand, Hoppen and Wormald [15] have recently developed a technique for translating many results for random r-regular graphs to rregular graphs with sufficiently large girth. In particular, they are able to translate bounds obtained by analyzing the performance of so-called locally greedy algorithms for a random regular graphs. These algorithms and their analysis provide the currently best known asymptotic bounds to many parameters of random regular graphs, for example an upper bound on the size of the smallest dominating set [START_REF] Duckworth | On the independent domination number of random regular graphs[END_REF]. The main tool for the analysis of such algorithms as well as for analysis of many other random processes is the differential equation method developed by Wormald [START_REF] Wormald | Differential Equations for random processes and random graphs[END_REF].

Bounds on maximum edge-cuts are closely related to the concept of fractional cut coverings. A fractional cut covering of a graph G is a parameter analogous to a fractional coloring of G. It was first introduced by Šámal [START_REF]On XY mappings[END_REF] under the name cubical colorings; he also related this parameter to graph homomorphisms. These ideas are further developed in [START_REF]Fractional covering by cuts[END_REF][START_REF]Cubical coloring fractional covering by cuts[END_REF]. The aim is to assign non-negative weights to edge-cuts in G in such a way that for each edge e of G the sum of weights of the cuts containing e is at least one. The fractional cut covering number is the minimum sum of weights of cuts forming a fractional cut covering. Our approach in this paper gives also an upper bound for the fractional cut covering number of cubic graphs with sufficiently large girth.

New results

The main result of this paper is the following. Theorem 1. There exists an absolute constant g 0 such that the following holds. If G is a cubic graph with girth at least g 0 , then there exists a probability distribution on edge-cuts in G such that each edge of G is contained in an edge-cut drawn according to this distribution with probability at least 0.88672.

Proof of the Theorem 1 actually provides that g 0 ≤ 637 789. Before presenting the proof of Theorem 1, let us state four corollaries of this theorem. First, by considering the expected size of an edge-cut drawn according to the distribution from Theorem 1, we get the following.

Corollary 2. There exists an absolute constant g 0 such that every n-vertex cubic graph with girth at least g 0 contains an edge-cut of size at least 1.33008n.

We can also translate Theorem 1 to subcubic graphs with large girth. Corollary 3. There exists an absolute constant g 0 such that the following holds. If G is a graph with maximum degree at most three and girth at least g 0 , then there exists a probability distribution on edge-cuts in G such that each edge of G is contained in an edge-cut drawn according to this distribution with probability at least 0.88672. In particular, G contains an edge-cut of size at least 0.88672m, where m is the number of edges of G.

Proof. Fix g 0 to be the constant given by Theorem 1, and let n 1 and n 2 be the numbers of vertices of G with degree one and two, respectively. Clearly, we may assume that G has no isolated vertices. Let R be a (2n 1 + n 2 )-regular graph with girth at least g 0 . There exists such a graph, since a random cubic graph has with positive probability girth at least g 0 for every fixed value of g 0 , which was proven by Bollobás [START_REF] Bollobás | A probabilistic proof of an asymptotic formula for the number of labelled regular graphs[END_REF] and independently by Wormald [START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF]. Replace each vertex of R with a copy of G in such a way that the edges of R are incident with vertices of degree one and two in the copies of G and the resulting graph is cubic. Observe that the obtained graph H has girth at least g 0 .

Consider the probability distribution D given by Theorem 1 on edge-cuts in H and fix an arbitrary copy G ′ of the graph G in H. For every edge-cut C ⊆ E(G) in G, we set the probability p(C) to be the probability that the edge-cut in G ′ induced by a random edge-cut in H drawn according to D is equal to C. This yields a probability distribution on edge-cuts in G with the required property.

Since a random cubic graph asymptotically almost surely contains only o(n) cycles shorter than a fixed integer g [START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF], the lower bound on the size of an edge-cut also translates to random cubic graphs. Proof. Again, fix g 0 to be the constant given by Theorem 1 and let G be a randomly chosen n-vertex cubic graph. The results of [START_REF] Wormald | The asymptotic distribution of short cycles in random regular graphs[END_REF] imply then we can a.a.s. remove o(n) vertices and obtain a subgraph G ′ with girth at least g 0 .

Therefore, G ′ has at least 1.5no(n) edges and by Corollary 3, there exists an edge-cut C ′ in G ′ of size at least 1.33008no(n). Suppose that X ⊆ V (G ′ ) is one of the sides of C ′ and let Y be the vertices removed from G. The edge-cut in G with one side being X ∪ Y has size at least 1.33008no(n).

The last corollary relates our results to the problem of fractional coverings the edges with edge-cuts. We show how to construct from the probability distribution given by Corollary 3 a fractional cut covering.

Corollary 5. There exists an absolute constant g 0 such that every n-vertex graph G with maximum degree at most three and girth at least g 0 has the fractional cut covering number at most 1.127752.

Proof. Fix g 0 to be the constant given by Theorem 1 and consider the probability distribution on edge-cuts in G given by Corollary 3. If the probability of an edge-cut C to be drawn in this distribution is p(C), assign C weight p(C)/0.88672. It is straightforward to verify that we have obtained a fractional cut covering of weight 1/0.88672 ≤ 1.127752.

Structure of the proof

Our proof is inspired by the method which was developed by Lauer and Wormald in [START_REF] Lauer | Large independent sets in regular graphs with large girth[END_REF] for finding large independent sets in regular graphs with large girth. This method was then extended by Hoppen [START_REF] Hoppen | Properties of graphs with large girth[END_REF], who improved the lower bound for independent sets and also proved a lower bound for induced forests. The latter result can also be found in [START_REF] Hoppen | Induced forests in regular graphs with large girth[END_REF].

In order to prove Theorem 1, we design a randomized procedure for obtaining an edge-cut which resembles the procedure used in [START_REF] Díaz | Bisection of Random Cubic Graphs[END_REF]. The main difference between our procedure and the procedure from [START_REF] Díaz | Bisection of Random Cubic Graphs[END_REF] is that our procedure finds an edge-cut whose parts have slightly different sizes, while the procedure from [START_REF] Díaz | Bisection of Random Cubic Graphs[END_REF] finds an edge-cut whose parts have the same size. Surprisingly, at least at the first glance, this edge-cut constructed in an asymmetric way is larger than an edge-cut from [START_REF] Díaz | Bisection of Random Cubic Graphs[END_REF].

The key tool for our analysis is the independence lemma (Lemma 7) which is given in Section 5. This lemma is used to simplify the recurrence relations appearing in the analysis. The recurrences describing the behavior of the randomized procedure are derived in Section 6. The actual performance of the procedure is based on setting up the parameters of the procedure and solving the recurrences numerically. This is discussed in Section 7.

The sought probability distribution is obtained by processing a cubic graph G = (V, E) by the procedure which produces an edge-cut in it. G is processed in a fixed number of rounds K and the required assumption on the girth of G will depend only on the number K. We will iteratively construct two disjoint subsets R ⊆ V and B ⊆ V ; the vertices contained in R are referred to as red vertices and those in B as blue ones. The aim of the procedure is to maximize the number of red-blue edges. The vertices that are neither red nor blue will be called white.

All vertices are initially white. In every round, each white vertex is recolored to red or blue with a certain probability depending on the number of its red and blue neighbors, as well as on the number of current round. Once a vertex is colored red or blue, its color stays the same in all the remaining rounds of the procedure.

Detailed description

We now describe the randomized procedure in more detail. We first introduce some notation. Let

I j := {(r, b) : r ∈ N 0 , b ∈ N 0 , r + b ≤ j}, i.e.
, the set I j contains all pairs r and b of non-negative integers such that r + b ≤ j. For example, I 2 = {(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (0, 2)}. Note that

|I j | = j+2
2 . Let G = (V, E) be a cubic graph and v a vertex of G. Throughout the analysis, r(v) will refer to the number of red neighbors of v and b(v) to the number of its blue neighbors. Therefore, 3r(v)b(v) is the number of the white neighbors of v. If the vertex v is clear from the context, we just use r and b instead of r(v) and b(v).

Our randomized procedure is parametrized by the following parameters:

• an integer K,

• probabilities P r,b k (W ) for all k ∈ [K] and (r, b) ∈ I 3 ,
• probabilities P r,b k (R) for all k ∈ [K] and (r, b) ∈ I 3 and

• probabilities P r,b k (B) for all k ∈ [K] and (r, b) ∈ I 3 . We require that P r,b k (W )+P r,b k (R)+P r,b k (B) = 1 for all k ∈ [K] and (r, b) ∈ I 3 .
The precise values of these probabilities will be defined in Section 7.

The integer K ∈ N 0 denotes the number of rounds that are performed. Throughout the procedure, vertices of the input graph G have one of the three colors: white (W), red (R) and blue (B). Let W k ⊆ V (G) denote the set of white vertices after the k-th round. Analogously, we define R k and B k as the sets of red vertices and blue vertices, respectively. As we have already mentioned, at the beginning of the process W 0 := V, R 0 := ∅ and B 0 := ∅.

= ∅ for all (r, b) ∈ I 3 \ {(0, 0)}.
Consider the coloring of G obtained after the k-th round. The (k + 1)-th round of the procedure is performed as follows. Let v be a vertex from W r,b k . With probability P r,b k+1 (R) we change the color of v to red, with probability P r,b k+1 (B) we recolor it to blue, and with probability P r,b k+1 (W ) it remains white. If v is after the k-th round colored red or blue, it will not change its color during the (k + 1)-th round.

Before we can proceed further, we have to introduce some additional notation. For a vertex v ∈ V (G) let T d v denote the subgraph of G induced by vertices at the distance from v at most d. Observe that if the girth of G is larger than 2d + 1, then the subgraph T d v is a tree. We show that if the girth of G is sufficiently large, then the probabilities that after the k-th round a vertex v has white, red or blue color, respectively, do not depend on the choice of v. To do so, let is start with the following proposition. Proposition 6. Let G be a cubic graph and v a vertex of G. For every k ∈ [K] the probability that the subgraph T K-k v has a certain coloring after the k-th round is determined by the coloring of T K-k+1 v after the (k -1)-th round.

Proof. The color of a vertex u ∈ T K-k v after the k-th round depends only on the colors of u and its neighbors after the (k -1)-th round. Since all the neighbors of u are contained in T K-k+1 v , the proposition follows.

Suppose that the girth of G is at least 2K. For any k ∈ [K] the structure of a subgraph T K-k v does not depend on the choice of v, i.e., it is always a tree with all inner vertices of degree three. Therefore, by a simple inductive argument on k together with Proposition 6, we conclude that all the following probabilities do not depend on the choice of v:

w k := P v ∈ W k , r k := P v ∈ R k , b k := P v ∈ B k .
Analogously, for any k ∈ [K -1] and (r, b) ∈ I 3 , the probability that after the k-th round a vertex v is white and has r red neighbors and b blue neighbors does not depend on the choice of v as well. Therefore, we can define w r,b k :

= P v ∈ W r,b k v ∈ W k .
If the girth of G is at least 2K + 1, the same reasoning as before yields the following. The probability that for an edge uv ∈ E(G) either u is red and v is blue after the k-th round, or v is red and u is blue after the k-th round does not depend on the choice of uv. This probability will be denoted by

p k := P (u ∈ R k ∧ v ∈ B k ) ∨ (u ∈ B k ∧ v ∈ R k ) .

Independence lemma

In this section we present a key tool we used in the analysis of the randomized procedure. In general, our analysis follows the approach used in [START_REF] Hoppen | Properties of graphs with large girth[END_REF].

If G is a cubic graph with girth at least 2K + 1, uv is an edge of G and d is an integer between 0 and K -1, T d v,u denotes the component of T d vu containing the vertex v. We refer to v as to the root of T d v,u . From the assumption on the girth it follows that all the subgraphs T d v,u are isomorphic to the same rooted binary tree T d of depth d.

Let k ∈ [K]. For a set V ′ ⊆ V (G) let c k (V ′
) denote the coloring of vertices V ′ after the k-th round. The set of all colorings of T K-k such that the root of the tree is white is denoted by C k . Observe that by the girth assumption and Proposition 6, for any γ ∈ C k the probability P c k T K-k v,u = γ does not depend on the edge uv.

We are ready to prove the main lemma of this section.

Lemma 7 (Independence lemma). Consider the randomized procedure with parameters K and P r,b i (C), where i ∈ [K], (r, b) ∈ I 3 and C ∈ {W, R, B}. Let G be a cubic graph with girth at least 2K + 1, uv an edge of G, k an integer smaller than K and γ u and γ v two colorings from C k . Conditioned by the event uv ⊆ W k , the events

c k T K-k v,u = γ v and c k T K-k u,v
= γ u are independent. In other words, the probabilities

P c k T K-k v,u = γ v uv ⊆ W k (1)
and

P c k T K-k v,u = γ v v ∈ W k ∧ c k T K-k u,v = γ u (2)
are equal.

Proof. The proof proceeds by induction on k. After the first round each vertex has a color C with probability P 0,0 1 (C) independently of the colors of the other vertices. Hence, the claim holds for k = 1.

Assume now that k > 1. By the definition of the conditional probability and the fact that the event uv ⊆ W k immediately implies that the event uv ⊆ W k-1 occurs, ( 1) is equal to

P c k T K-k v,u = γ v ∧ u ∈ W k uv ⊆ W k-1 P uv ⊆ W k uv ⊆ W k-1 . (3)
Analogously, ( 2) is equal to

P c k T K-k v,u = γ v ∧ c k T K-k u,v = γ u uv ⊆ W k-1 P v ∈ W k ∧ c k T K-k u,v = γ u uv ⊆ W k-1 . (4)
We now expand the numerator of (3).

γ ′ u ∈C k-1 γ ′ v ∈C k-1 P c k-1 T K-k+1 u,v = γ ′ u uv ⊆ W k-1 × P c k-1 T K-k+1 v,u = γ ′ v v ∈ W k-1 ∧ c k-1 T K-k+1 u,v = γ ′ u × P u ∈ W k c k-1 T K-k+1 u,v = γ ′ u ∧ c k-1 T K-k+1 v,u = γ ′ v × P c k T K-k v,u = γ v c k-1 T K-k+1 u,v = γ ′ u ∧ c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k .
By the induction hypothesis, for any two colorings γ ′ u , γ ′ v ∈ C k-1 the probabilities

P c k-1 T K-k+1 v,u = γ ′ v v ∈ W k-1 ∧ c k-1 T K-k+1 u,v = γ ′ u and P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 are equal.
Since the new color of u is determined only by the colors of the neighbors of u, it follows that the probabilities

P u ∈ W k c k-1 T K-k+1 u,v = γ ′ u ∧ c k-1 T K-k+1 v,u = γ ′ v and P u ∈ W k c k-1 T K-k+1 u,v = γ ′ u ∧ v ∈ W k-1 are also equal.
Analogously, for any vertex w ∈ T K-k v,u \ {v} the new color of w does not depend on γ ′ u at all. Applying the same reasoning for v yields that the probabilities

P c k T K-k v,u = γ v c k-1 T K-k+1 u,v = γ ′ u ∧ c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k and P c k T K-k v,u = γ v c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1
are equal as well. Note that in the last equality we have also used that the random choices of new colors for two arbitrary vertices in the (k + 1)-th round are independent.

By changing the order of summation, we conclude that the numerator of ( 3) is equal to

γ ′ u ∈C k-1 P c k-1 T K-k+1 u,v = γ ′ u uv ⊆ W k-1 × P u ∈ W k c k-1 T K-k+1 u,v = γ ′ u ∧ v ∈ W k-1 × γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P c k T K-k v,u = γ v c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1 .
Along the same lines, the denominator of ( 3) is equal to

γ ′ u ∈C k-1 P c k-1 T K-k+1 u,v = γ ′ u uv ⊆ W k-1 × P u ∈ W k c k-1 T K-k+1 u,v = γ ′ u ∧ v ∈ W k-1 × γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P v ∈ W k c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1 .
Canceling out the sum over γ ′ u which is the same in both numerator and denominator of (3), we derive that ( 1) is equal to

γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P c k T K-k v,u = γ v c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1 × γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P v ∈ W k c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1 -1 . ( 5
)
We apply the same trimming to the numerator and denominator of ( 4). The numerator is first expanded to

γ ′ u ∈C k-1 P c k-1 T K-k+1 u,v = γ ′ u uv ⊆ W k-1 × P c k T K-k u,v = γ u c k-1 T K-k+1 u,v = γ ′ u ∧ v ∈ W k-1 × γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P c k T K-k v,u = γ v c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1
and the denominator is then expanded to

γ ′ u ∈C k-1 P c k-1 T K-k+1 u,v = γ ′ u uv ⊆ W k-1 × P c k T K-k u,v = γ u c k-1 T K-k+1 u,v = γ ′ u ∧ v ∈ W k-1 × γ ′ v ∈C k-1 P c k-1 T K-k+1 v,u = γ ′ v uv ⊆ W k-1 × P v ∈ W k c k-1 T K-k+1 v,u = γ ′ v ∧ u ∈ W k-1 .
By canceling out the sum over γ ′ u , we obtain [START_REF] Díaz | Computation of the bisection width for random d-regular graphs[END_REF]. Therefore the expressions ( 1) and ( 2) are equal.

Recurrence relations

In this section we derive recurrence relations for the probabilities describing the behavior of the randomized procedure.

Fix parameters K and P r,b k (C) for k ∈ [K], (r, b) ∈ I 3 and C ∈ {W, R, B}. We will inductively show that the probabilities describing the state of the procedure after the (k + 1)-th round can be computed using only the probabilities describing the state after the k-th round. This yields the recurrence relations for the probabilities, which is the main goal of this section.

We start with determining the probabilities after the initialization round. It is easy to see that the probabilities r 1 , b 1 , w 1 , p 1 and w r,b 1 are

r 1 = P 0,0 1 (R) , b 1 = P 0,0 1 (B) , w 1 = 1 -r 1 -b 1 , p 1 = 2 • P 0,0 1 (R) • P 0,0 1 (B) and w r,k 1 = 3 r 3 -r b • P 0,0 1 (R) r • P 0,0 1 (B) b • 1 -P 0,0 1 (R) -P 0,0 1 (B) 3-r-b for (r, b) ∈ I 3 .
Next, we show how to compute the probabilities r k+1 , b k+1 and w k+1 from r k , b k , w k and w r,b k . We start with the formula for r k+1 . If a vertex v is colored red after the (k + 1)-th round, then after the k-th round, it was either already colored red, or it was white, had r red neighbors, b blue neighbors and it was recolored to red. The latter happened with probability P r,b k+1 (R). The probability of the first event is r k and that of the second event is

w k • w r,b k • P r,b k+1 (R)
. This yields that

r k+1 = r k + w k • (r,b)∈I 3 w r,b k • P r,b k+1 (R) .
Analogously, we can compute

b k+1 = b k + w k • (r,b)∈I 3 w r,b k • P r,b k+1 (B) ,
and finally w k+1 is given by

w k+1 = 1 -r k+1 -b k+1 .
Before we proceed with the recurrences for p k+1 and w r,b k+1 , let us introduce some auxiliary notation. All of the following quantities are fully determined by w r,b k , but this notation will help to make the formulas simpler. We start with probability that a vertex v has white color after the (k + 1)-th round conditioned by the event it had white color after the k-th round. This quantity will be denoted by w →k+1 . It is straightforward to check that

w →k+1 := P v ∈ W k+1 v ∈ W k = (r,b)∈I 3 w r,b k • P r,b k+1 (W ) .
Next, we consider the probability that the vertex u is white after the k-th round conditioned by the event that a fixed neighbor v of u is white after the k-th round. This will be denoted by q W -W k . We claim that

q W -W k := P uv ⊆ W k v ∈ W k = (r,b)∈I 2 3 -r -b 3 • w r,b k .
First observe that the events v ∈ W r,b k , where (r, b) ∈ I 3 , form a partition of the event v ∈ W k , and for (r, b) ∈ I 3 \ I 2 the probability that u is white after the k-th round is equal to zero. Suppose that v ∈ W r,b k , i.e., it has r red neighbors, b blue neighbors (and 3rb white neighbors) after the k-th round. This happens with probability w r,b k . Since u is a fixed neighbor of v, it has white color after the k-th round with probability (3rb)/3.

Finally, for a color C ∈ {W, R, B} and an edge e = uv, q

(C)
→k+1 denotes the probability that u has the color C after the (k + 1)-th round conditioned The analysis just presented yields that

p k+1 = p k + w k 3 • (r,b)∈I 3 w r,b k • P r,b k+1 (R) • 2b + (3 -r -b) • q (B) →k+1 + w k 3 • (r,b)∈I 3 w r,b k • P r,b k+1 (B) • 2r + (3 -r -b) • q (R) →k+1
.

We finish this section with the recurrence relations for the probabilities w r,b k+1 . Observe that

w r,b k+1 = P v ∈ W r,b k+1 P v ∈ W k+1 = P v ∈ W r,b k+1 v ∈ W k P v ∈ W k+1 v ∈ W k . ( 6
)
The second equality holds because each of the events v ∈ W k+1 and v ∈ W r,b k+1 immediately implies that the event v ∈ W k occurs. The denominator of ( 6) is equal to w →k+1 , so it remains to derive the formula for numerator.

Let N W k (v) denote the set of white neighbors of v after the k-th round. Using the same argument as for deriving the formula for p k+1 , the color after the (k + 1)-th round of a white neighbor u ∈ N W k (v) will be red with probability q (R) →k+1 . Analogously, it will be blue with probability q (B) →k+1 and white with probability q (W ) →k+1 . By Lemma 7 and the fact that in all rounds we recolor each white vertex independently of the others, the new color of a neighbor u 1 ∈ N W k (v) does not depend on the new color of another neighbor u 2 ∈ N W k (v). Now consider the probability that a vertex v is white and has r red and b blue neighbors after the (k+1)-th round, i.e., v ∈ W r,b k+1 , conditioned by the event v ∈ W r,b k , where r ≤ r and b ≤ b. This probability is denoted by w r,b→r,b →k+1 . We claim that w r,b→r,b →k+1 is equal to ways. The probability that all vertices in Y will be red after the (k + 1)-th round is equal to q (R) →k+1 r-r . Analogously, all vertices in Z will be blue after the (k +1)-th with probability

P r,b k+1 (W ) • 3 -r -b r -r 3 -r -b b -b • q (R) →k+1 r-r • q (B) →k+1 b-b • q (W ) →k+1

Setting up the parameters

In this section we set up the parameters in the procedure. In the first round, we pick a vertex with a small probability p 0 and color it either red or blue. The next rounds of the procedure are split into two phases, which consist of K 1 and K 2 rounds, respectively. Therefore, the total number of rounds K is equal to

K 1 + K 2 + 1.
In the rounds of the first phase, with probability p B (p R ), where p R ≪ p B , we color a vertex with exactly one red (blue) neighbor by blue (red). If a vertex has at least two neighbors of the same color, we color it with the other color with probability one. In all the other cases we do nothing.

With one exception, the rounds of the second phase are performed identically to the rounds of the first phase. The exception is that a white vertex with one red, one blue and one white neighbor is colored red with probability p RB /2 or blue with probability p RB /2. The choice of p RB is such that p RB ≪ p R .

Specifically, we set:

• K := K 1 + K 2 + 1, • P 0,0 1 (R) := p 0 /2 , P 0,0 1 (B) := p 0 /2 , • P r,b k (R) := 1 for (r, b) ∈ I 3 ∩ {(r, b) : b ≥ 2} for k ∈ [2, . . . , K] , • P r,b k (B) := 1 for (r, b) ∈ I 3 ∩ {(r, b) : r ≥ 2} for k ∈ [2, . . . , K] , • P 0,1 k (R) := p R , P 1,0 k (B) := p B for k ∈ [2, . . . , K] , • P 1,1 k (R) := p RB /2 , P 1,1 k (B) := p RB /2 for k ∈ [K 1 + 2, . . . , K] ,
• P r,b k (R) := 0 for all the other choices of r and b,

• P r,b k (B) := 0 for all the other choices of r and b and The choice of K 1 was made in such a way that at the end of the first phase, i.e., after the (K 1 + 1)-th round, the probability that a vertex is white and has exactly one non-white neighbor is less than 10 -7 . Analogously, the choice of K 2 was made in a way that at the end of the process, i.e., after the K-th round the probability that a vertex is white is less than 10 -7 .

• P r,b k (W ) := 1 -P r,b k (R) -P r,b (
The code of the C program used for the computation can be downloaded from http://iuuk.mff.cuni.cz/~volec/cubic-cut/. The output of the program with all the values of variables p k , r k , b k , w k and w r,b k for k ∈ [K] and (r, b) ∈ I 3 computed for the given choice of parameters can also be found on the web page. For the floating-point calculations, the program uses the MPFR library for a high-precision floating-point calculations with correct rounding [START_REF] Fousse | MPFR: A multiple-precision binary floating-point library with correct rounding[END_REF]. We used the running error analysis method (see, e.g., Section 2.5.1 from [START_REF] Dahlquist | Numerical Methods in Scientific Computing[END_REF], or Section 3.3 from [START_REF] Higham | Accuracy and Stability of Numerical Algorithms, Second Edition[END_REF]) to upper bound the rounding error coming from the representation of floating-point numbers. Setting the length of the mantissa of all the floating-point variables to 657400, we upper bound the rounding error for all p K , r K and b K by 2 -657400 × 10 197862 < 10 -35 .

Solving the recurrences for the above choice of parameters we have obtained that p K > 0.88672. The probability that a vertex v is colored red at the end of the process, i.e. r K , is equal to 0.491979 and the probability that b K is equal to 0.508021. In Figures 1234, we plot the evolution of the probabilities p k , r k , b k , w k , w 0,0 k , w 0,1 k and w 1,1 k . The vertical dashed line in each figure correspond to the end of the first phase. The probabilities w 0,2 k , w 0,3 k , w 1,0 k , w 1,2 k w 2,0 k , w 2,1 k and w 3,0 k are less than 10 -3 for every k ∈ [K]. The above choice of the parameters is not the best possible. In particular, setting smaller values for the parameters p RB , p R and p 0 would produce a slightly larger edge-cut at the cost of stronger assumption on the required girth. On the other hand, computer experiments on random cubic graphs of size 10 7 suggest that optimizing the parameters of this procedure cannot obtain significantly better upper bound than 0.88696. The presented method is also applicable for d-regular graphs for d ≥ 4 analogously as the Hoppen's method [START_REF] Hoppen | Properties of graphs with large girth[END_REF] could be used for translating the results of Díaz, Do, Serna and Wormald [START_REF] Díaz | Bounds on the max and min bisection of random cubic and random 4-regular graphs[END_REF] and Díaz, Serna and Wormald [START_REF] Díaz | Computation of the bisection width for random d-regular graphs[END_REF].

Corollary 4 .

 4 A random n-vertex cubic graph asymptotically almost surely contains an edge-cut of size at least 1.33008no(n).

  For (r, b) ∈ I 3 we define W r,b k ⊆ W k to be the set of white vertices with exactly r red neighbors and b blue neighbors. Hence the sets W r,b k forms a partition of W k for every k. Note that W 0,0 0 = V and W r,b 0

.

  Indeed, v stays white after the (k + 1)-th round with probability P r,b k+1 (W ). Next, fix two disjoint subsets Y and Z of N W k (v) of sizes rr and bb, respectively. This can be done in3-r-b

,

  and the vertices in N W k (v)\(Y ∪ Z) will be white after the (k+1)th round with probability q for every (r, b) ∈ I 3 .

  B) for (r, b) ∈ I 3 . The recurrences presented in this chapter were solved numerically using a computer program. The particular choice of parameters used in the program was p 0 = 2 -18 , p B = 1, p R = 2 -11 , p RB = 2 -17 , K 1 = 34 919 and K 2 = 283 974 (and hence K = 318 894).

Figure 1 :

 1 Figure 1: Evolution of p k

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Evolution of r k and b k

Acknowledgments The authors would like to thank Nick Wormald for pointing out the reference [19] and the anonymous referees for careful reading the manuscript and their valuable comments improving the presentation of the results.

This author was supported by Slovak Research and Development Agency under the contract no. APVV-0023-10. This work was done when the author was affiliated with Institute for Theoretical Computer Science of Charles University (ITI), which was supported as project 1M0545 by Czech Ministry of Education. This author was also supported by the grant GACR 201/09/0197.

by the event that both u and v were white after the k-th round. We infer from the definition of the conditional probability that q (R)

We are now ready to present the remaining recurrences. Let us start with p k+1 , i.e., the probability than an edge e = uv is red-blue after the (k + 1)-th round. Note that once we color a vertex x with either red or blue color, the color of x in the future rounds will stay the same. Therefore, we can split the contribution to p k+1 to the following four types.

1. e ∩ W k = ∅ : This event happens with probability p k and the colors stay the same.

2. e ∩ W k = {v} : Suppose first that u is blue after the k-th round.

The probability that we have such configuration after k-th round is

In this case, the edge e become red-blue after the (k + 1)-th round with probability P r,b k+1 (R). Analogously, if u is red after the k-th round, the contribution of this case is

3. e ∩ W k = {u} : This case is symmetric to the previous one.

4. e ⊆ W k : The probability that v has white color after the k-th round is

, v has r red neighbors, b blue neighbors, and u is white after the k-th round. The probability that v becomes red after the (k + 1)-th round is P r,b k+1 (R), and using the independence lemma (Lemma 7) the neighborhood of u does not depend on the colors of the other neighbors of v. Therefore, the probability that u becomes blue after the (k + 1)-th round is q (B) →k+1 . On the other hand, the probability that after the (k + 1)-th round v becomes red and u becomes blue is P r,b k+1 (B) • q (R) →k+1 .