High output h 90% Low input l =

Analysis of Probabilisti Non-interferen e 1

Alessandro Aldini z

MarioBravetti y

Roberto Gorrieri y

z

IstitutoSTI, UniversitadiUrbino,Italy,

aldinisti.uniurb.it

y

DipartimentodiS ienzedell'Informazione,UniversitadiBologna, Italy,

fbravetti,gorrierig s.unibo.it

Abstra t

We dene several se urity properties for theanalysis of probabilisti

non-interferen easa onservativeextensionofa lassi al,nondeterminis-

ti ,pro ess-algebrai approa htoinformation owtheory. Weshowthat

probabilisti overt hannels (whi hare notobservable inthe nondeter-

ministi setting) mayberevealedthroughour approa hand that prob-

abilisti information anbeexploitedto give anestimateofthe amount

of ondential information owing to unauthorized users. Finally, we

present a ase studyshowing thatthe expressivenessof the al ulus we

adoptmakesitpossibletomodelandanalyzereal on urrentsystems.

1 Introdu tion

The analysis of information ow among dierent omponents of a on urrent

omputer systemis awell establishedapproa h used for preventing unautho-

rizeddis losureof ondentialinformation(see,e.g.,[8,4,31,28℄). Amongthe

dierent proposals whi h address su h an analysis, we onsider the notion of

non-interferen e[31℄that expressesapriva ypropertyofsystems. The entral

idea of non-interferen eis that aprogram is se ure wheneverthe variation of

the ondentialdata does notae t theprogram behavioras observedby an

external atta ker. The original notionofnon-interferen ewasdened for sys-

tem programswhi hare deterministi . Generalizednotionsof noninterferen e

werethendesignedtoin ludenondeterministi systemsonthebasisofdierent

systemmodels(see,e.g.,[61,42,40℄)andherewe on entrateontheuseofpro-

essalgebras(see,e.g.,[36, 48,47,23,45, 50℄). Inparti ular,in thispaperwe

onsider thenondeterministi approa hby Fo ardiand Gorrieri[23℄and their

lassi ation of a set of se urity properties apturing the idea of information

1

Preliminaryresultsofthispaperappearedin:A.Aldini,\Probabilisti InformationFlow

in aPro ess Algebra",Pro . of12thInt. Conf.onCon urren y Theory(CONCUR2001),

Springer LNCS 2154:152-168 and A.Aldini, \On the Extension of Non-interferen ewith

Probabilities",2ndACMSIGPLANandIFIPWG1.7WorkshoponIssuesintheTheoryof

Se urity(WITS2002).

whereeventsarepartitionedintotwodierentlevelsof ondentiality(lowlevel

andhighlevel),thusallowingtheinformation owingbetweenthetwodierent

levelstobemodeledand ontrolled. Asanexample,themostintuitiveproperty

theyadvo ateistheNonDedu ibilityonCompositions(NDC),whoseintuitive

idea is that an atta kershould notbeable to inferanything aboutthe on-

dentialintera tionsof thesystemwith thehigh-levelenvironment. Informally,

it anbedes ribedasfollows:

82HighUsers: EjEw:r:t:LowUsers

where E isthemodelof the systemtobe onsidered,jstands forthe parallel

ompositionoperator,istheequivalen erelationonthebehaviorasobserved

bylowusers. Theaboveformula saysthat E is NDC se ure if, fromthe low-

leveluserstandpoint,thebehaviorofthesystemisinvariantwithrespe ttothe

omposition withanyhigh-leveluser.

Possibilisti noninterferen e for nondeterministi pro esses abstra ts away

from further aspe ts of the system behaviorwhi h ould be exploited by the

atta kerto set upa overt hannel. Forinstan e, aswewill formally showin

anexampleborrowedfrom[51℄ (whi hin turn isinspiredby[42℄), onsider an

atta kexploitingthefrequen yofthepossibleout omes(derivingfromrepeated

exe utionsof thesystem) in orderto infer ondentialinformation ( ommuni-

ated by high users)that otherwise is notrevealed by onsidering the nonde-

terministi behavioronly. In parti ular, assume that ase ret 1-bit value an

be ommuni atedto theunauthorized useramong randomly reatedlow-level

noiseandthatbothse retvalueandrandomlow-levelnoisebelongtothesame

domain(0 and1):

lowinputl :=(highoutputhorrandomvalue):

Thehighbehavior,expressed bythedire tassignmentof htol,doesnotalter

the set of possiblelowout omes that is always the samewith orwithout the

high-levelintera tion. However,byobserving thefrequen y ofea hlowresult

deriving from repeatedexe utions of thesystem, anatta ker ouldbeableto

infer (with a ertain probability) whi h one is dire tly ommuni ated by the

highuser(seeFig.1). Therefore,whileinanondeterministi settingthesystem

isse uresin ethe hoi ebetweenthetwoassignmentsisleft underspe ied,in

ari herframework,wheretheprobabilitydistribution ofthepossibleeventsis

known,itispossibletorevealanunwantedinformationleakage.

Anotherreasonfor onsideringprobabilitiesisthataprobabilisti approa h

permitsto over omethe lassi al,qualitative,binary viewa ordingto whi h

highinformationisorisnotleakedtolowusers. Morepre isely,by omputing

theprobabilityasso iatedtothehigh-levelbehaviorswhi h anbedistinguished

by lowusers, themodeler anestimate thelevelof se urityof thesystem. In

pra ti e, an observer may he k if the probability of dete ting an illegal in-

Random value High output h

value Random 90% 10%

Probabilistic Setting

High output h Low input = l

Low input = l

Possibilistic Setting

Figure1: Con ealedprobabilisti overt hannel

se ure \enough". For instan e, by onsidering the exampleabove, if the low

inputltakesthevalueofthehighoutputhwithanegligibleprobability" lose

to 0, then the interferen e of the high user during thesystem exe ution may

be onsidered insuÆ ient to set up a real, ee tive overt hannel from high

level to lowlevel. This quantitative approa h to information ow analysis is

parti ularly usefulfor theveri ationof real systems, wherethe interplaybe-

tweenhighusersandlowbehaviorsismoretightthanthat weexpe t[49℄ and

themaingoal onsistsofminimizingtheillegalintera tions,bykeepingthein-

evitableinformation owsatana eptablelevel. Asasimple,realexample,note

thatpassword-basedauthenti ationsystemsarebeyondthes opeofpossibilis-

ti information- owte hniques,whi hreje t programswhi h donotguarantee

absolutese re y. Indeed,atypi albrute-for epolynomial-timeatta kmaytry

to he keverypossiblepasswordto ra kthesystem,buttheprobabilityofsu -

ess, i.e. the potentialinformation leakage, is negligibly small (see, e.g., [60℄).

Asanexample,wewill formallyevaluatetheee tivenessof su hanatta kin

aseoftheauthenti ationsystemofanautomati tellerma hine(asdone,e.g.,

in [19℄).

Inthispaper,weapplytheapproa htoinformation owtheoryof[23℄toa

nondeterministi pro essalgebraand,inthe ontextofaprobabilisti extension

of su h a al ulus, we propose a natural, onservative, probabilisti extension

ofthese uritypropertiesdes ribedin [23℄. With respe tto [23,24,25℄, whi h

arebasedonaCCS-likepro essalgebra,hereweresorttoaCSP-like al ulus,

that makesit easyandnaturalthedenition oftheprobabilisti modeland is

parti ularly adequate to ombine powerfulme hanisms(likeexternal/internal

hoi es, multiwaysyn hronization,andasyn hronousexe utionofparallelpro-

esses)that are suitableto des ribe thebehaviorofreal, omplexsystems (as

emphasized,e.g.,in[1℄). Theextensionweproposeis onservativein thesense

thatbyremovingprobabilisti informationfromasystemP ofourprobabilisti

al ulusweobtainthenondeterministi variantP

nd

ofP,onwhi htheapproa h

to information owtheorybasedonnondeterminismof[23℄maybeappliedby

analysis of P. In parti ular, if P satises agiven se urity property S in our

probabilisti framework,then P

nd

satisesthe orrespondingnondeterministi

propertyS

nd

and,ingeneral,intheprobabilisti settingwehavethesamein lu-

sionrelationshipsamongse uritypropertiesasinthenondeterministi setting.

Therefore,aswewillshowthroughseveralexamples,ourprobabilisti se urity

properties apturebothinformation owswhi h areobservableby onsidering

thelogi al behaviorsof thesystemand information leakagedue to theproba-

bilisti behaviorofthesystemonly. Moreover,weshowhowprobabilities anbe

exploited to a hieveadditional information related to the information owing

throughthe system,like, e.g.,the se uritylevel ofthe systemin the sense we

spe iedabove.

Finally, allthe main featuresof ourprobabilisti approa hare emphasized

ina asestudy. Morepre isely,wemodelthealgebrai spe i ationofarouter

workingat thenetwork layerand implementingaprobabilisti routingme ha-

nism that handlesboth ondentialandpubli data. With these assumptions

inview,weanalyzedierentversionsofsu hasystemthatmayrevealpotential

possibilisti andprobabilisti information owsfrom highleveltolowlevel.

1.1 Related Work

A signi ant amount of work has been done in order to extend the relation

among potentialinformation owsand dierentaspe ts of on urrentsystems

su hastimeandprobabilities. Asanexample,programswhi hexe uteseveral

on urrentpro essesintrodu ethepotentialforamali iouspartytoobservethe

internal timing behaviorsof programs, viatheee t that therunning time of

ommands mighthaveonthes heduler hoi e ofwhenevervarious on urrent

alternatives anbe exe uted (see, e.g., [26, 22, 54℄). On the other hand, real

systems may exhibit probabilisti overt hannels that are not ruled out by

standard nondeterministi se urity models [32, 61℄. In parti ular, Gray [32℄

proposesinthe ontext ofaprobabilisti versionof Millen'ssyn hronousstate

ma hine [43℄ twodenitions of se urity: (i) theProbabilisti Non-interferen e

(PNI), whi h intuitively saysthat dierent behaviorsof the high part of the

environmentdonotae ttheprobabilitydistributionofthelowevents(su han

intuition,aswewillsee,willberephrasedinourpro ess-algebrai setting);(ii)

theAppliedFlowModel(AFM),whi h isaninterpretation oftheFlowModel

of[42℄,sayingthattheprobabilityofalowoutputmaydependonpreviouslow

events,butnotonprevioushighevents. GrayprovesthatAFM isstrongerthan

PNI (similarly,wewillpresentanotionofse uritystrongerthanourdenition

ofPNI). Moreover,Jurjens[37℄ onsidersthenotionofPNI of[32℄inthesetting

ofamodelofprobabilisti data ow,byshowingthe ompositionalityofPNI in

su h a ontext and that asimplernonprobabilisti notionof non-interferen e,

alledNondedu ibilityonStrategies[61℄,isaninstantiation ofPNI.

upaprobabilisti overt hannelwherebyinformationisobtainedbystatisti al

inferen es drawn from the relative frequen y of out omesof a repeated om-

putation". Therefore, they formalize the idea of ondentiality for a simple

imperative language with dynami thread reation. More pre isely, they de-

velopextensionalsemanti s basedspe i ationsof se ureinformation ow for

multi-threadedprograms. Su hspe i ations aptureprobabilisti information

owsthatarisefromthes hedulingof on urrentthreads. Thenoveltyoftheir

approa histheadoptionofaprobabilisti notionofbisimulationinformalizing

se urity onditions (as previouslydone in [23℄ in anondeterministi setting).

In[55℄, atypesystemispresentedthat aimstoensurese ureinformation ow

in asimplemultithreaded imperativeprogramminglanguagerunningundera

uniform probabilisti s heduler. Thesameauthoralsoproposesadenition of

weak probabilisti bisimulation (inspired by [7℄) in [56℄ to justify the orre t-

nessofatypesystemforse ureinformation ow. Inthesamelineoftheabove

dis ussion, [16℄ resortsto apossibilisti information ow analysis of aProba-

bilisti IdealisedAlgolto he kforprobabilisti interferen e,whereasin[18,19℄

aprobabilisti se urity analysis is proposed in theframework of ade larative

programminglanguage.Finally,in[33,58℄amodallogi issetoutforreasoning

aboutmultilevelse urityofprobabilisti systems.

However,to thebestof ourknowledge,no approa hhasbeenproposed for

thedenitionoftheinformation owtheoryinthe ontextofaprobabilisti pro-

essalgebra. Wethink thatthedenition andtheanalysisofinformation ow

se uritypropertiesfor on urrentsystems ouldbenetbythewell-established

supportgivenbytheknownresultsandformalte hniquesdevelopedin (proba-

bilisti ) pro essalgebrasthat,astheliteraturehasshownin thenondetermin-

isti ase(see,e.g.,[45,24,50℄),oertheadequatetoolfora leanandrigorous

formalizationofageneralizednotionofse urity.

1.2 Outline

Theremainderofthepaperisorganizedasfollows. Westartbyintrodu inga

simplenondeterministi pro essalgebraandbyprovidingasaba kgroundthe

denition of three se uritypropertiesin the sameline ofthe nondeterministi

approa hof[23℄(Se t.2). Then,wepresenttheprobabilisti extension[2,10,9℄

ofthenondeterministi al ulusofSe t.2,obtainedbyaddingprobabilisti pa-

rameterstothealgebrai operators(Se t. 3). Asfarastheequivalen erelation

weadopt is on erned,weresortto aprobabilisti variantoftheweakbisimu-

lation(Se t. 4),themain reasonbeingthatweakbisimulationhasbeenproved

tobeparti ularlysuitabletodealwithsomekindofinformation owfornonde-

terministi pro esses[23,24℄. Basedonsu hanotionofequivalen e, wedene

the probabilisti version of the properties of Se t. 2 and we make a ompar-

ison between thenondeterministi setting and su h a probabilisti framework

revealed bydierent versions of thesamesystem(Se t. 6). Finally, wereport

some on lusions(Se t.7)and theproofsofresults(seetheappendix).

2 Possibilisti Se urity Properties

Inthisse tion,werephrasethepossibilisti approa htoinformation owtheory

of[23,24, 25℄,whi h employaCCS-like al ulus,inthe ontextofanondeter-

ministi pro essalgebrawhi hisasynthesisofCCS[44℄andCSP[35℄.

2.1 A Nondeterministi Cal ulus

Inournondeterministi al ulus,a tionsareexpli itlypartitioned into output

a tions and input a tions and a multiway ooperation dis ipline is applied in

ordertoallowsyn hronizationsinvolving(atmost)oneoutputa tionand(pos-

sibly several) input a tions to be performed. As we will see, these features

simplify the denition of the probabilisti model when extending the nonde-

terministi pro essalgebrawithprobabilities. Asusual inse uritymodels, we

distinguishbetweenhigh-levelvisiblea tionsandlow-levelvisiblea tionsinor-

dertoallowtheanalysisoftheinformation owbetweenparties withdierent

levelsof ondentialitytobeperformed.

Formally,wedenotethesetofa tiontypesbyAType,rangedoverbya;b;:::.

As usual, AType in ludes the spe ial type  denoting aninternal a tion. We

deneasetofinputa tionsbyI =fa



ja2AType fggand aset ofoutput

a tionsbyO=AType fg.The ompletesetofa tionsisdenotedbyA t =I[

O[fg,rangedoverby; 0

;:::. Moreover,wedenotetwodisjointsetsAType

H

and AType

L

of high-level and low-level a tion typeswhi h form a overing of

AType fg,su hthat a2O anda



2I arehigh (low)a tionsifa2AType

H

(a 2 AType

L

). Throughout the paper, we onsider h;h 0

;::: to be high-level

typesandl;l 0

;:::tobelow-leveltypes.

LetConst be aset of onstants, ranged overby A;B;:::. The set L

nd of

pro ess termsof our al ulusis rangedoverby P

nd

;Q

nd

;::: (when itis lear

fromthe ontextweomitthesubs riptnd)and isgenerated bythesyntax:

P ::=0j:P jP+P jPk

S

P jP=LjA

whereS;LAType fg.

Asfarasaninformalintuitionoftheoperatorsis on erned,0representsthe

terminated ordeadlo kedterm,:P isthe lassi alprexoperator,P+Qisa

CCS-likealternative ompositionoperatorexpressinganondeterministi hoi e

betweenP andQ,andPk

S

QisaCSP-likeparallel ompositionoperator,where

pro essesP andQ:

 lo allyexe utetheirinputandoutputa tionsoftypea62S;

Inparti ular, asyn hronizationbetween twoa tionsof type a2S may

o ur onlyif either theyare bothinput a tions a



(and the resultis an

inputa tiona



), oroneofthem isanoutputa tion aandtheotherone

isaninputa tiona



(andtheresultisanoutputa tiona).

Hen e,ourparalleloperator allowsmultiwaysyn hronizations omposedbyall

inputa tionsex eptat mostoneoutputa tiontobeperformed. Inparti ular,

thesyn hronizationpoli ywe onsiderisasymmetri ,inthatbyfollowingaso-

alledmaster-slave ooperationdis iplineapro ess anbroad astagivenoutput

a tiona, whileea hofthe otherpro essesrea tsbysyn hronizingthroughan

input a tion a



[10, 12℄. Moreover, we point out that the CSP-like parallel

operator anbeusedto expresstherestri tionofa tions. Inparti ular,Pk

L 0

represents asystem exe uting the lo al a tions whi h the lefthand pro ess P

anperformex ept for thea tionswhose type belongs to thesyn hronization

setL,whi harenotallowedtosyn hronizebe ausetherighthandpro essisthe

nullterm0. Therefore,forthesakeofsimpli ityweusetheabbreviationPnL,

denotingasystemP whi h preventstheexe utionof thea tionsbelongingto

thetypesetL,tostandfortheexpressionPk

L 0.

Then, we have the hiding operator P=L whi h turns the a tions of type

a2Lintointernal a tions. Finally, onstantsAareusedtospe ifyre ursive

systems.

Inthe following, we restri t ourselvesto the set G

nd

 L

nd

of losed and

guarded terms, i.e. we require that every onstant has exa tly one dening

equation(oftheformA

=P)andevery onstanto urren eiswithinthes ope

of an a tion prex operator [44℄. We denote by sort(P), with P 2 G

nd , the

setofa tionswhi hsynta ti allyo urinthea tionprexoperatorswithinP,

and byG

Hnd

=fP 2G

nd

jsort(P)AType

H

gtheset of high-level terms(i.e.

ontaining high-level a tions only). If P

1

! :::

n

!P 0

, with 

1

;:::;

n a

(possiblyempty)sequen e ofa tions in A t, then P 0

is aderivative of P. We

denote by Der(P) the set of derivatives of P. Finally, we dene a fun tion

t: A t!ATypethatmapsa tionsontothe orrespondinga tiontypes,namely

t()= if62I,andt(a



)=awitha

 2I.

Theformalsemanti sofournondeterministi pro essalgebraisgivenbythe

labeled transition system(L

nd

;A t;!),whose statesareterms ofthe pro ess

algebraandthetransitionrelation!L

nd

A tL

nd

istheminimalrelation

satisfyingtheoperationalrulesreportedin Table1.

Inordertodenese uritypropertiesinthe ontextofour al ulus,weneed

a notion of equivalen e relation. In parti ular, sin e we on entrate on the

observationalpowerof the low user (whi h is limited to the low-level events,

whilethehigh-levela tivitiesare onsideredasunobservable a tions)weneed

a notion of equivalen e whi h abstra ts from  a tions and fo uses only on

visible behaviors. Due tothis, weemployaweakbisimulationequivalen e[44℄

typi al of other notions of equivalen e, su h as the tra e equivalen e. The

notion of bisimulation is ner than tra e equivalen e and is able to dete t a

highernumberofinformation ows(e.g.,tra eequivalen eisnotabletodete t

high-leveldeadlo ks). Asfarasothernotionsofequivalen eare on erned,[24℄

showsthatfailure/testingequivalen esarenotadequateforsystemswithsome

high-levelloopsorwith loops.

Pre :P



!P

Sum

P



!P 0

P+Q



!P 0

Q



!Q 0

P+Q



!Q 0

Par

P



!P 0

Pk

S Q



!P 0

k

S Q

t()62S

Q



!Q 0

Pk

S Q



!Pk

S Q

0

t()62S

P a

!P 0

Q a

!Q 0

Pk

S Q

a

!P 0

k

S Q

0

a2S P

a

!P 0

Q a

!Q 0

Pk

S Q

a

!P 0

k

S Q

0

a2S

P a



!P 0

Q a



!Q 0

Pk

S Q

a

!P 0

k

S Q

0

a2S

Hid

P



!P 0

P=L



!P 0

=L

t()62L

P



!P 0

P=L



!P 0

=L

t()2L

Con

P



!P 0

A



!P 0

if A

=P

Table1: Operationalsemanti sforthenondeterministi al ulus

Inthe following, givenA  A t



, we say that P A

)P 0

if and only if there

exists w2A (withw=w

1 :::w

n

forsomen) andtermsP

i

(with 1in),

su hthat P wi

!P and P P andP 0

P . Moreover,given 2A t,

we use the abbreviation P



)P 0

to stand for P

 

)P 0

. In parti ular, P

^



)P 0

standsforP



)P 0

if2A t fgandforP





)P 0

if =. NotethatP

^



)P 0

meansthatzeroormore labeledtransitionso ur,while



) requires atleast

one labeledtransition.

Wenowreportthe lassi aldenitionofweakbisimulationovertermsofour

nondeterministi al ulus.

Denition2.1 ArelationRG

nd

G

nd

isaweakbisimulationif(P;Q)2R

impliesforall 2A t:

 wheneverP



!P 0

, then there exists Q 0

2G

nd

su h that Q

^



)Q 0

and

(P 0

;Q 0

)2R ,

 onversely, whenever Q



!Q 0

, then there exists P 0

2 G

nd

su h that

P

^



)P 0

and(P 0

;Q 0

)2R .

TwotermsP;Q2G

nd

areweaklybisimulationequivalent,denotedP 

B Q,

ifthere existsaweak bisimulationR ontainingthepair(P;Q). Itis provable

that 

B

isanequivalen erelation[44℄.

Finally, we use the expression P iso

= Q to say that P and Q are isomor-

phi ,i.e.thelabeledtransitionsystemsderivedfrom P andQare stru turally

equal(thereexists abije tion betweenthetwostatespa essu h thatanypair

of orresponding stateshaveidenti ally labeled transitions towardanypair of

orrespondingstates).

2.2 Analyzing Possibilisti Se urity Properties

Based on the above nondeterministi pro ess algebra and the related notion

of equivalen e, we now denethree se urityproperties in the line of [23℄. We

startwiththeBisimulationStrongNondeterministi Non-interferen e(BSNNI),

whi hinformallysaysthatasystemisse ureifwhatthelow-levelpart ansee

does notdepend onwhat the high-level part ando. Inourpro ess-algebrai

frameworkitmaybeexpressedasfollows.

Denition2.2 P 2G

nd

isBSNNI se ureifandonlyif

P=AType

H



B

PnAType

H :

IntheabovedenitionP=AType

H

representsasystemwhere thehigh-level

a tions are hidden, whilePnAType

H

represents asystemwhere the exe ution

of the high-level a tions is prevented. Therefore, if a system P satises the

BSNNI propertythen,fromthelow-leveluserviewpoint,thefollowing ondition

ispreserved: forea hbehaviorin PnAType

H

whi his observablewheneverthe

H

notvisible bythe lowview,and vi eversa. Inessen e, alow-level user annot

infer,byobservingthelowviewofthesystem,thatsomehigh-levela tivityhas

o urred.

Example2.3 Letus onsider thesystemP

=l:0+h:l 0

:0that,from thelow-

levelstandpoint,nondeterministi allyperformseitherana tionlorana tionl 0

ifthehigh-leveloutputhhaspreviouslyo urred.Whenanalyzingthese urity

propertiesofP,wemakethefollowingassumptions. Sin eweemploya al ulus

where ommuni ationsare syn hronous, system P intera ts with the external

environmentbyoering high (low)outputs whi h haveto bea eptedby the

high (low)userand by a eptinghigh(low) inputswhi h ome from thehigh

(low) user. For instan e, in the initial state of our example, system P an

either exe ute theoutput a tion l if the low user is available to a ept it, or

exe ute the output a tion h if thehigh user is available to a ept it. Hen e,

we he kiftheinterplaybetweenthehighuserandthehighpartofthesystem

an ae t the view of the system asobserved by a low user. Then, we also

assumethat thelowuserknowshowthesystemP is dened,andwe he kif,

inspiteofthis,heisnotabletoinferthebehaviorofthehighuserbyobserving

the low viewof the systemat run time. With these assumptionsin view, we

an verify that P is learly not se ure, be ause depending on whi h output

a tionbetweenlandl 0

isexe utedbythesystem,alowuser aninferthatthe

high userhas (hasnot)a epted theoutput a tionh. Formally, wehavethat

P=AType

H iso

=l:0+:l 0

:06

B l:0

iso

=PnAType

H .

Anotherexample of an unwanted information ow is given by the system

P

=l:P+h:0,whereapossibledeadlo k anbe ausedbytheexe utionofthe

high-levela tionh. Awareofsu hapotentialbehavior,alowuserknowsthat

nohigh-levela tionhasbeenperformedea htimeheobservesalow-levela tion

l. This is more thanenough to set up aninformation owfrom high levelto

lowlevel. Formally,wehavethatP=AType

H iso

=l:P+:06

B l:P

iso

= PnAType

H .

Note that the same system turns outto be BSNNI se ure if the equivalen e

relationweemployisthe lassi altra eequivalen ethat,hen e,isnotadequate

torevealhigh-leveldeadlo ks.

Finally, an example of a system whi h is BSNNI se ure is given by P

=

l:P+h:l:P. Indeed,the low-levelviewofP onsistsofthe repeatedexe ution

ofa tionl, thatis notenoughto inferanythingaboutthehigh-levelbehavior.

Formally,P=AType

H iso

=l:P+:l:P 

B l:P

iso

=PnAType

H .

Otherpropertieshavebeensuggestedinorderto apturedierentbehaviors

ofthesystemthathavetobe onsideredinse ure. Forinstan e,asalreadyseen

in theintrodu tion,oneof themostestablishedse uritypropertiesis theNon

Dedu ibility on Composition, whi h says that the low view of a systemP in

isolation isnot to bealtered when onsideringea h potential intera tionof P

the NDC property basedon thebisimulationequivalen e, alled Bisimulation

NDC (BNDC). Aformalizationofsu hapropertyinthe ontextofour al ulus

maybeasfollows.

Denition2.4 P 2G

nd

isBNDC se ureifandonlyif

PnAType

H



B ((Pk

S

)=S)nAType

H

;82G

H

nd

;8SAType

H :

Theleft-handtermrepresentsthelowviewofthesysteminisolation,while

theright-handterm expressesthelowviewofP intera ting with thehigh en-

vironment (note that the a tivities resulting from su h intera tions are made

invisible). Su h aformalization is ompliant to thedenition of BNDC given

in [25,24℄, where theonlydieren eistheadoption ofaCCS-likeparallel op-

erator. Inparti ular, dueto theCSP-likeparallel operatorof our al ulus,we

rsthide thehigh-levela tionsbelongingto S whi hsu eed in syn hronizing

in Pk

S

 andthenwepurgethesystemoftheremaininghigh-levela tions.

Example2.5 TermP

=l:0+h:h:l:0isBSNNI se ure. However,thehigh-level

part analterthelowviewofthesystemin asethehigh-leveluserrstexe utes

therst high-levela tionh andthen blo ks theexe ution ofthe se ond high-

levela tionh. Insu ha aseadeadlo kis ausedbythehighuserthatprevents

the low-level a tion l from being observed bythe low user. This information

ow is aptured by the BNDC property if we take 

= h



:0 and S = fhg.

Indeed, in su h a ase we have PnAType

H iso

= l:0 6

B

l:0+:0 

B

(((l:0+

h:h:l:0)k

S (h



:0))=S)nAType

H .

Be auseofthepresen eoftheuniversal quanti ationonallpossiblehigh-

level pro esses, theBNDC property ould be diÆ ult to be used in pra ti e.

Therefore, strongerformulations of su h aproperty have been proposed that

avoid the adoption of universal quanti ation on all possible high-level pro-

esses and reveal additional potential information ows that some authors in

the literature onsider to beinse ure. Here, wede ide to onsider theStrong

BNDC (SBNDC), introdu ed in [23℄, that does notinvolve omposition with

ea h possible high-level pro ess  and is the strongest se urity property de-

nedby theauthors of [23℄. In[29,46℄ the sameproperty under thename of

stronglo al non-interferen e(SLNI)hasbeenproposedfortheanalysisofnon-

interferen einthe ontextofCSP [35℄. LiketheBNDC property,theSBNDC

he ksthe onditionwhi hsaysthatwhateverthehigh-levelpartdoes,theset

ofnondeterministi behaviors whi h areobservablebythelowusershould not

hange. Moreover,asastri terrequirement,italso he ksthe onditionwhi h

says that wheneverthe low user observesthe systembehavior, he should not

distinguish whi h, if any, high-level event has o urred at some point in the

al ulusisasfollows.

Denition2.6 P 2 G

nd

is SBNDC se ure if and only if 8P 0

2 Der(P) and

8P 00

su hthat P 0



!P 00

; t()2AType

H

;then

P 0

nAType

H



B P

00

nAType

H :

Withrespe ttothedenitionofBNDC,wherewehaveto he ktheproperty

foraninnitesetofterms,i.e.82G

H

nd

,the onditionneededbytheSBNDC

requires to he kanitenumberofterms, i.e.ea h P 0

2Der(P),wheneverP

isasso iatedto anitestatetransitionsystem.

Example2.7 Letus onsidertermP

=:(:0+:l:0)+:h:l:0fromwhi hthe

labeledtransitionsystemofFig.2(a)isderived. P isBSNNI se ure. Formally,

P=AType

H iso

=:(:0+:l:0)+::l:0and,byfollowingthe-lawsof[44℄,wehave

:(:0+:l:0)+::l:0

B

:(:0+:l:0)

B

:(:0+:l:0)+:0 iso

= PnAType

H .

Moreover,itisprovablethatP isBNDCse uretoo. Informally,withorwithout

theintera tionofhighuserswhi ha epttheoutputa tionh,thesystemevolves

either into adeadlo k state orinto a state where l, whi h is the only a tion

observablebyalowuser,isexe uted. However,P doesnotsatisfytheSBNDC

property, be ausethe lowview in stateP 0

=h:l:0, rea hable from P through

the exe utionof aninternal a tion, depends onwhether the high-level output

hisexe uted. Morepre isely,atransitionlabeledwiththea tionhleadsfrom

P 0

to P 00

=l:0andP 0

nAType

H iso

=06

B l:0

iso

= P 00

nAType

H

. Intuitively, it an

bedebatablewhetherweshould lassifyP asaninse uresystem. Forinstan e,

one may argue for this being an information ow be ause, on e the internal

nondeterminism is resolved, the system an evolve into a state where ahigh

user anblo k(ordelay)theexe utionofthelow-levela tionl,thus reatinga

overt hannel. Ontheother hand,it isworthnotingthat thehigh-levelpart

hasno ontrolovertheresolution ofthenondeterminismin termP.

Example2.8 Asanotherexample,inFig.2(b)weshowthelabeledtransition

system asso iated to term Q

= h:l:0+:l:0+l 0

:0, whi h is BSNNI se ure

(QnAType

H iso

= :l:0+l 0

:0 

B

:l:0+:l:0+l 0

:0 iso

= Q=AType

H

) and BNDC

se uretoo. Inparti ular,foranyhighuserwhi hintera tswithQbya epting

thehigh-leveloutputh,thelowviewofthesystem onsistsofanondeterministi

hoi e betweenl 0

andaninternala tionwhi hleadstotheexe utionofa tion

l. Ontheotherhand,foranyhighuserwhi hdoesnotallowtheoutputa tion

hto beexe uted,the lowviewof thesystemstillremainsthesame. However,

we annot onsiderQasase uresystem,be ausealowuserwhi hobservesthe

a tionl 0

andedu ethatthehighuserhasnotperformedthea tionh. Inother

exe utionofthehigh-levela tionhleadsfromQtoQ 0

=l:0,butQnAType

H iso

=

:l:0+l 0

:06

B l:0

iso

=Q 0

nAType

H .

Example2.9 Asanalexample,whi hhasbeenproposedin [46℄,letus on-

sider the following system R

= :l

0 :R+h

0

:l

0

:R +:l

1 :R+h

1

:l

1

:R , where

the high-level environment repeatedly ommuni ates a value (0 or 1) to the

low-levelpartamongstrandomly reatednoise(seetheunderlyinglabeledtran-

sition systemin Fig.2( )). One anbelievethat R hasno information owif

we onsiderthepossiblebehaviorsofthesystemonly. IndeedRisbothBSNNI

(R nAType

H



B

:l

0 :R+:l

1 :R

B

R =AType

H

)and,asitiseasytosee,BNDC

se ure. Anyway, ea h timethe a tionl

0 (l

1

) isexe utedalowuserinfers that

thehigh-levelinputh

1

 (h

0



)hasnottaken pla e. Moreover,in [46℄it issug-

gested that the low user should be able to infer the high behavior whenever

the high user always oers theinput h

0



with respe t to theinput h

1

 . For-

mally, the system R doesnot satisfy the SBNDC property. For instan e, R

an exe ute the high-level a tion h

0

thus rea hing the state R 0

= l

0 :R , but

R nAType

H iso

=:l

0

:R+:l

1 :R6

B l

0 :R

iso

=R 0

nAType

H .

h h

h

h

l ₀ l ₁

l

R

τ τ

1 * 0 _*

l ₁ l ₀

R R

R R

(c) (b)

(a)

l τ τ

τ P τ

P ^’

Q τ

l l

l ^’

Figure2: ExamplesofsystemsthatareBNDC se ure,butnotSBNDC se ure

We on ludethis introdu tory se tionbyobservingthat thein lusion rela-

tionshipsforthebisimulation-basedse uritypropertiesdepi tedin Fig.3hold.

Proposition2.10 SBNDC BNDC BSNNI.

Inthis se tionweproposed thenondeterministi non-interferen eproperty,

whi histheinterpretationinapro ess-algebrai settingofthenon-interferen e

notionof[31℄, thenondedu ibilityon ompositionproperty,whi hwe onsider

the most intuitive property proposed in [23℄, and a strong (and easier to be

veried)versionofsu haproperty[23℄. We on ludebyobservingthat many

other properties exist and they all an be rephrasedin our nondeterministi

pro essalgebrabypreservingthein lusionrelationshipshownin [23,25℄.

SBNDC BNDC BSNNI

Figure3: In lusionrelationshipamong nondeterministi properties

3 A Cal ulus with Probabilities

In this se tion, we onsider a probabilisti extension of the nondeterministi

pro ess algebra of Se t. 2.1. Su h a al ulus is a slight variant of a pro ess

algebra proposed in [2, 10, 9℄ and expresses both nondeterministi behaviors

and probabilisti information. This is a novelty with respe t to the existing

models used to formalize a probabilisti notion of non-interferen e, whi h do

notmodelnondeterminismbutjust probabilisti behaviors.

Aswewillsee,themostnaturalandintuitivewaytodenesu hanextension

onsistsof:

1. addingprobabilisti informationtothealgebrai operators;

2. adoptinga model of probabilities,that turns outto beamixture of the

lassi algenerativeandrea tivemodelsof[30℄.

In parti ular, we assume that output a tions behave asgenerative a tions: a

pro ess whi h behaves generatively autonomously de ides, on the basis of a

probabilitydistribution,whi ha tionwill beperformed. Moreover,weassume

thatinputa tionsbehaveasrea tivea tions: apro esswhi hbehavesrea tively

just rea ts internally to the a tion hosen by a generative omponent of its

environment(saya) onthe basisof aprobabilitydistribution asso iated with

therea tivea tionsoftypeait anperform. Therefore,sin ethe hoi eofthe

a tion type is ompletelynondeterministi , asitdepends onthe environment,

we see the rea tive a tions as in omplete a tions that must syn hronize with

generativea tionsofanothersystem omponentinordertoforma losedsystem

(i.e. asystem notin luding nondeterministi hoi es that haveto beresolved

bytheenvironment). Then,asystemis onsideredtobefullyspe iedwhenit

gives riseto aprobabilisti transition systemthat is purely generative, in the

sensethatitexe utes ompletea tionsonly. Afullyspe iedsystemistherefore

afullyprobabilisti systemfromwhi haMarkovChain,whi h anbeanalyzed

togetperforman emeasuresofthesystem, anbeeasily derivedbydis arding

rea tivetransitionsystems,asso iatedtotermsofthe al ulusbytheoperational

semanti s,andthenwepresentthesyntaxandthesemanti s. Finally,weequip

the al uluswithaweakprobabilisti bisimulationequivalen einthelineof[7℄.

3.1 Generative-rea tive Transition Systems

Generative-rea tivetransitionsystemsare omposedoftransitionslabeledwith

ana tion,whi h anbeeitheroutputorinput,andaprobability. A ordingto

our hoi e of onsidering input a tions asrea tivea tions and output a tions

as generativea tions, wedenote the set of rea tivea tions by R A t= I and

the set of generativea tions by GA t = O[fg. Note that the a tion  is

generative, be ause it expresses an internal move autonomously exe uted by

thepro ess withoutintera tionswiththeenvironment. Moreover,it turnsout

that A t=RA t[GA t.

Transitions leaving a state are grouped into several bundles. We have a

singlegenerativebundle omposedofallthetransitionslabeledwithagenerative

a tion,andseveralrea tivebundles,ea honereferringtoadierenta tiontype

aand omposed ofallthetransitions labeledwith a



. A bundleof transitions

expressesaprobabilisti hoi e. Onthe ontrary, the hoi e amongbundles is

performednon-deterministi ally.

Denition3.1 Agenerative-rea tivetransitionsystem(GRTS,forshort)isa

triple (S;AType;T)where S is a set of states,AType is aset of a tion types,

andT 2M(SA t℄0;1℄S)isamultiset 2

ofprobabilisti transitions,su h

that:

1. 8s2S;8a



2RA t;

P

fjpj9t2S:(s;a



;p;t)2Tjg2f0;1g

2. 8s2S;

P

fjpj9a2GA t;t2S:(s;a;p;t)2Tjg2f0;1g

A rooted GRTS is atuple (S;AType;T;s

0

), with s

0

2 S theinitial state and

(S;AType;T)aGRTS.

Requirement 1denes therea tivebundles (one forea h a tiontype) and

requirement2denestheuniquegenerativebundle. Bothrequirementssaythat

for ea h statethe probabilitiesof thetransitions omposing abundle, if there

areany,sumupto1(otherwisethesummationoveremptymultisetsisdened

equalto0). Asanexample,inFig.4weshowaGRTS omposedofagenerative

bundleenablingthreetransitionsa,b,and ,area tivebundleoftypeeenabling

twotransitionse



,and area tivebundle oftypedenablingasingletransition

d



. Graphi ally, transitions of the same bundle are grouped by an ar , and

2

We use\fj" and \jg"as bra kets for multisets and M(S) to denote the olle tion of

multisetsoverS. We usemultisets tohandle the parti ular ase inwhi h froma state s

severaltransitions(labeledwiththesamea tionandprobabilityp)leadtoastatet.

a,

c, b,

* , q

* , 1−q d *

pq p(1−q)

1−p e

e

Figure4: Exampleofagenerative-rea tivetransitionsystem

the probability ofa transition isomitted whenequalto 1. Wepointoutthat

a fully spe ied system(i.e. a systemthat doesnot in lude rea tivebundles)

is performan e losed, in the sense that it gives rise to a fully probabilisti

transitionsystemthatdoesnotin ludenondeterministi hoi es.

Finally, it is easy to see that from agenerative-rea tive transition system

we an derive alabeled transition system (L

nd

;A t;!) asthose des ribed in

Se t.2.1bysimplyremovingtheprobabilitiesfromthelabelsofthetransitions.

3.2 Syntax and Informal Semanti s

ThesetLofpro esstermsofour al ulus,rangedoverbyP;Q;:::,isgenerated

bythesyntax:

P ::=0j:P jP+ p

P jPk p

S P jP=

p

a jA

where S  AType fg, a 2 AType fg, and p 2℄0;1[. We denote by G

the set of guarded and losed terms (i.e. the set of pro esses of L) and by

G

H

=fP 2Gjsort(P)AType

H

gthesetofhigh-levelpro esses,i.e.in luding

high-levela tionsonly.

AninformaloverviewoftheoperatorsisverysimilartothatgiveninSe t.2.1,

ex ept forthefa t that herewehaveprobabilisti parametersatta hedto the

operatorsthatweemploytoresolvethe hoi esinea hpro essterm. Indeed,it

isworthnotingthatfrom anytermP 2L we anderivea orrespondingterm

P

nd 2L

nd

byremovingthe probabilisti parametersfrom theoperators in P.

Asanexample,pro essP

=l:0+

p

h:h:l:0isaterminLanditsnondeterministi

ounterpartispro essP

nd

ofExample2.5. Now,weshowtheintuitivemeaning

ofea hoperator.

0representsaterminatedordeadlo kedtermhavingnotransitions.

Theprex operator:P performsthea tion withprobability1and then

behaveslikeP. 3

Thealternative ompositionoperatorP+ p

Qexpressesaprobabilisti hoi e

betweenthegenerativea tionsofP andQandbetweentherea tivea tionsof

P andQofthesametype. Inparti ular,wehavethefollowing ases:

3

Usually,weabbreviateterms:0byomittingthenal0 .

1. ifbothP andQ anexe ute generativea tions, then P+ Q hoosesa

generativea tion of P with probability p and a generative a tion of Q

withprobability1 p. See,e.g.,Fig.5(a);

2. ifonepro essP orQ annotexe utegenerativea tions,P+ p

Q hooses

agenerative a tion of the other pro ess with probability 1(similarly as

in[6℄);

3. asfarasrea tivea tionsofagiventypeaare on erned,P+ p

Q hooses

betweenthe rea tivea tions a



of P and Q a ording to probability p,

byfollowing thesame me hanism seen forgenerativea tions. See, e.g.,

Fig.5(b);

4. the hoi e among generative and rea tive a tions oramong rea tive a -

tionsofdierenttypesisjustnondeterministi . See,e.g.,Fig.5( )whi h

showspurelynondeterministi hoi esandFig.5(d)whi hshowsamixed

nondeterministi /probabilisti hoi e.

a+ p

b b

 +

p

b



a+ p

b

 a

 +

p

b



(a+ p

0

b

 )+

p

(b+ p

00

b

 )

p 1−p

(a)

a, b,

* , 1−p , p

*

(b)

b b

* * *

(c)

a b a b

* , p * , 1−p

p 1−p

(d)

a, b, b b

Figure5: ExamplesofGRTSsderivedfromalternative omposition

Theparallel omposition operator Pk p

S

Q performs thea tions of its om-

ponentsP andQbyfollowingthesyn hronizationpoli ydes ribedinSe t.2.1

and,forthea tionsofPandQnotinS,thesameprobabilisti me hanismseen

foralternative omposition. Moreover,itfollowstheseadditionalrules:

1. sin ethe exe utionofsomegenerativea tionof P (Q) anbeprevented

inPk p

S

Q,theprobabilitiesofexe utingtheremaininggenerativea tions

of P (Q) are proportionally redistributed so that their overall probabil-

ity sumsupto 1(as standardwhen restri tinga tions in thegenerative

model[30℄);

2. in aseofsyn hronizinggenerativea tionsaofP (Q),theirprobabilityis

distributedamongthemultiple a tionsaobtainedbysyn hronizingwith

rea tivea tionsa



exe utablebyQ(P),a ordingtotheprobabilitythe

a tionsa



are hoseninQ(P);

3. in aseofsyn hronizingrea tivea tionsof agiventypea2S, ifbothP

andQ anexe utesomea tion a , the hoi e ofthetwoa tionsa ofP

andQformingthea tionsa



exe utablebyPk

S

Qismadea ordingto

theprobabilitythattheyareindependently hosenbyP andQ.

Example3.2 InFig.6(a)wereporttheGRTS derivedfromterm((a+ q

b)+ q

0

 )k

p

f g

thatmayexe utethetwonon-syn hronizinggenerativea tionsaand

bofthelefthandpro essandthesyn hronizinggenerativea tion oftheright-

hand pro ess (note that the exe ution of is allowed by the rea tive a tion



of thelefthand pro ess). As in ase of alternative omposition, sin eboth

pro essesmayexe utesomegenerativea tions,weperformagenerativea tion

ofthelefthand pro esswith probabilitypandagenerativea tionof theright-

handpro esswithprobability1 p. Sin ethegenerativea tionsexe utableby

(a+ q

b)+ q

0



areawith probability qand b withprobability1 q, the om-

posedsystemexe utesa tionawithprobabilityp
q,a tionbwithprobability

p
(1 q)anda tion withprobability1 p.

Asanotherexample,inFig.6(b)weshowtheGRTS derivedfromtheterm

(a+ r

b)k p

fa;bg (b

 : +

q

b



:d),whereonlythelefthandpro essmayexe utesome

generativea tion(hen eparameterpisnot onsidered). Inparti ular,sin ethe

righthandpro ess doesnotallowthea tion ato syn hronize,weexe uteonly

thegenerativea tionbwithprobability1(hen eparameterrisnot onsidered).

Su h an a tion syn hronizes with one of the two rea tive a tions b

 of the

righthand pro ess hosen a ording to probability q. Therefore, we exe ute

the a tion b leading to 0k p

fbg

with probability q and the a tion b leading to

0k p

fbg

dwithprobability1 q.

b,

b, q 1−q

c d

(b)

a,

c, pq

1−p b, p(1−q) (a)

Figure6: ExamplesofGRTSsderivedfrom parallel omposition

ThehidingoperatorP=

p

a

turnsgenerativeandrea tivea tionsoftypeainto

generativea tions, by hangingtheprobabilitiesa ordingtotheserules:

 as farasgenerativea tionsexe utable byP=

p

a

are on erned, wedistin-

guishthefollowing ases:

1. if P enables both some generativea tion and some rea tive a tion

a



, then P=

p

a

hooses agenerative a tion  (obtained by hiding an

a tion a



of P) with probability p and a generative a tion previ-

ously enabled in P with probability 1 p. Su h arule guarantees

that thehidingoperatordoesnotintrodu enondeterminismamong

generativea tionsbypreservingtherequirement2ofdenition3.1;

2. ifeither P doesnotenablegenerativea tions,orP doesnotenable

rea tivea tionsa



, theninP=

p

parameterpisnot onsidered;

 asfar asrea tive a tions are on erned, P=

a

enables the same rea tive

a tions(withthesameprobabilitydistribution) oftypeb6=aenabledin

P.

Example3.3 Letus onsiderthepro essP

=a

 +

q 0

(b+ q

),wherethe hoi e

amonga



andthegenerativea tionsband ispurelynondeterministi (param-

eter q 0

is not onsidered). The semanti s of P=

p

a iso

=  + p

(b+ q

), where the

a tionoftypeaofP isturnedintoa a tion,isaprobabilisti hoi ebetween

, exe uted with probability p,and thea tions b and ,exe uted withproba-

bility(1 p)
qand(1 p)
(1 q),respe tively. Hen e,parameterpexpresses

theprobabilitythat a tion obtainedby hidingtherea tivea tiona



of P is

exe utedwithrespe tto thegenerativea tionspreviouslyenabledbyP.

Thereasonforturningrea tivea tionsa



intogenerativeinternala tions

dependsonthefa tthatoneofthegoalsofthehidingoperator onsistsofob-

tainingfullyspe iedsystemsfromopen systems(i.e.systemsenablingrea tive

hoi es). In parti ular, when a systemis fully spe ied, the nondeterministi

hoi es due to the possible intera tions with the environment have to be re-

solved,andparameterpturnssu h hoi esintoprobabilisti hoi es. Formally,

the ee t of hidingtherea tivea tiona



in pro ess P orresponds to theex-

e ution of a syn hronization between a



and an external generativea tion a

that givesrise to an internal a tion  whose probabilitydistribution depends

on parameterp. Whenanalyzing se uritypropertieswhi hemploy thehiding

operator,wewillshowthatthelowbehaviorofase uresystemdoesnotdepend

onthe hoi eofparameterp.

ConstantsA areused tospe ifyre ursivesystems. Whendening analge-

brai spe i ation,weassumeasetof onstantsdening equationsoftheform

A

=P (withP aguardedterm)tobegiven.

Forthesakeofsimpli ity, weassume:

 theparameterpto beequalto 1

2

wheneveritisomittedfromanyproba-

bilisti operator;

 thesyn hronizationsetStobetheemptysetwheneveritisomittedfrom

theparalleloperator;

 the abbreviation P=

p1:::pn

a1:::an

to denote the expression P=

p1

a1 :::=

pn

an whi h

hidesa tionsof severaltypes;

 theabbreviationP=S, with a

1 :::a

k

asequen e oftypesin AType fg

andS=fa

1

;:::;a

k

gtherelatedset oftypes,tostandforP=

a1:::a

k when

ea h termin Der(P)doesnotenablerea tivea tions oftype in S. It is

easytoseethat,insu ha ase,theprobabilisti parametersofthehiding

operators are not meaningful and, in parti ular, P=

a

1 :::a

k iso

= P=

p1:::pk

a1:::ak ,

8p ;:::;p 2℄0;1[.

therestri tionofa tions. Hen e,weusetheabbreviationPnLto standforthe

pro ess Pk

L

0denoting the restri tion of the a tions with type in the set L.

Sin e the null term annot perform any move, the probabilisti parameterin

theparalleloperatorisnot onsidered,i.e.Pk

L 0

iso

=Pk p

L

08p2℄0;1[.

Inordertoavoidambiguities,weintrodu ethefollowingoperatorpre eden e

relation: prex>restri tion=hiding>alternative omposition>parallel om-

position. Finally,wepointoutthat parameterpoftheprobabilisti operators

annotbeequaltothelimitingvalues0and1,sin einour al ulusaprobabilis-

ti hoi edoesnotex ludethe exe ution ofapossiblebehaviorof thesystem

(instead,extremalprobabilities anbeusedtoexpresspriorities[57℄).

3.3 Operational Semanti s

Theformalsemanti s ofour al ulusisgivenbythegenerative-rea tivetransi-

tionsystem(G;AType;T),whosestatesaretermsofthe al ulusandthetran-

sitionrelationT istheleastmultisetsatisfyingtheoperationalrulesreportedin

Table2andinTable3,whereinadditiontoruleswhi hrefertothelo almoves

of the lefthand pro ess P, wealso onsider the symmetri alrules taking into

a ountthelo almovesoftherighthandpro essQ,obtainedbyex hangingthe

roles of terms P and Q in the premises and by repla ing p with 1 pin the

labelofthederivedtransitions.

As far as the notation is on erned, we use P



!P 0

to stand for 9p :

P

;p

!P 0

, meaningthat P anexe utea tion  with probabilitypand then

behaveasP 0

,P



! tostandfor9P 0

:P



!P 0

,andP G

! tostandfor

9a2 G AType : P a

!, meaning that P an exe utea generativea tion

of atype belonging to set G. Here, we detailthe rules of Table3 on erning

thegenerativetransitionsexe utablebyPk p

S

Q,while itiseasyto seethat all

otherrulesre e ttheinformaldes riptionof theoperatorsgivenin Se t.3.2.

Sin ewe onsiderarestri tedsetofexe utablea tions,likein[30℄weredis-

tributetheprobabilitiesofthegenerativetransitionsofP exe utablebyPk p

S Q

sothattheiroverallprobabilitysumsupto1(we ansymmetri allyargueforQ).

Tothis aim, in semanti sruleswe employthefun tion 

P

(G):P(AType) !

℄0;1℄,with P 2 G, dened as 

P (G) =

P

fjpj9P 0

;a 2 G : P a;p

!P 0

jgthat

omputesthe sumof theprobabilitiesof thegenerativetransitionsexe utable

by P whose type belongs to set G. Note that the set of types of the gener-

ative transitions of P exe utable by Pk p

S

Q is omposed by the a tion types

not belonging to thesyn hronization set S and the a tiontypes belonging to

S forwhi h asyn hronizationbetweenagenerativea tionofP andarea tive

a tion of Qis allowed to be performed. Therefore,in 

P

(G) ifwetakeasset

Gthe set G

S;Q

AType, withS AType fgand Q2G, tobedened as

G

S;Q

=fa2ATypeja62S_(a2S^Q a



!)g, thenwehavethat 

P (G

S;Q )

byPk p

S

Qand anbeusedtonormalizetheprobabilitiesofthegenerativetran-

sitionsof P. Moreover,note that theprobabilityof the generativetransitions

a (with a 2S) of P arefurther distributed among the rea tive transitions of

typeaofQ. Finally,parameterpisusedtoredistributetheprobabilitiesofthe

normalizedgenerativetransitionsofP andQexe utablebyPk p

S Q.

Asshownin[2,10℄wehavethattheoperationalsemanti sofapro essP 2G

isaGRTS.

:P

;1

!P

P a



;q

!P 0

Q a

!

P+ p

Q a;p
q

!P 0

P a



;q

!P 0

Q a

!

=

P+ p

Q a;q

!P 0

P a;q

!P 0

Q GA t

!

P+ p

Q a;p
q

!P 0

P a;q

!P 0

Q GA t

!

=

P+ p

Q a;q

!P 0

P a;q

!P 0

P GA t

!

P=

p

a

;p
q

!P 0

= p

a

P a;q

!P 0

P GA t

!

=

P=

p

a

;q

!P 0

= p

a

P b



;q

!P 0

P=

p

a b



;q

!P 0

= p

a

a6=b

P b;q

!P 0

P a



!

P=

p

a

b;(1 p)
q

!P 0

= p

a

a6=b P

a;q

!P 0

P a



!

P=

p

a

;(1 p)
q

!P 0

= p

a

P b;q

!P 0

P a



!

=

P=

p

a b;q

!P 0

= p

a

a6=b P

a;q

!P 0

P a



!

=

P=

p

a

;q

!P 0

= p

a

P

;q

!P 0

A

;q

!P 0

if A

=P

Table2: Operationalsemanti s(partI)

P !P 0

Q



!

Pk p

S Q

a



;p
q

!P 0

k p

S Q

a62S

P !P

0

Q



!

=

Pk p

S Q

a



;q

!P 0

k p

S Q

a62S

P a;q

!P 0

Q a;q

0

!Q 0

Pk p

S Q

a



;q
q 0

!P 0

k p

S Q

0

a2S

P a;q

!P 0

Q G

S;P

!

Pk p

S Q

a;p
q=P(GS;Q)

!P 0

k p

S Q

a62S

P a;q

!P 0

Q GS;P

!

=

Pk p

S Q

a;q=P(GS;Q)

!P 0

k p

S Q

a62S

P a;q

!P 0

Q a;q

0

!Q 0

Q GS;P

!

Pk p

S Q

a;p
q 0

q=

P (G

S;Q )

!P 0

k p

S Q

0

a2S

P a;q

!P 0

Q a;q

0

!Q 0

Q G

S;P

!

=

Pk p

S Q

a;q 0

q=

P (G

S;Q )

!P 0

k p

S Q

0

a2S

Table3: Operationalsemanti s(partII)

4 Equivalen e

In this se tion wedene theweakprobabilisti bisimulation equivalen e, pro-

posedin[7℄,inthe ontextofgenerative-rea tivetransitionsystems. Thebasi

idea onsists of repla ing the lassi al weak transitions s

^



)s 0

used in Deni-

tion 2.1by the probability to rea h the lass ofstates equivalentto s 0

from s

viaasequen eoftransitionslabeledwithstringsin



^





. Beforeintrodu ing

su hanotionofequivalen e,were allsomebasi notationrelatedtoprobability

theory(see,e.g.,[34℄).

Probabilitytheory beginswith the on eptofprobabilityspa e, whi h isa

triple(;F;P),where:

 thesample spa e isanonemptysetofelements, alledsample points;

 the probability measure P is an assignment of a real number P(F) to

every event F of the sigma eld su h that (i) P(F)  0 for all F 2

F, (ii) P() = 1, (iii) if F

i

(with i = 1;2;:::;n) are disjoint, then

P(

S

n

i=1 F

i )=

P

n

i=1 P(F

i

),(iv)ifF

i

(withi=1;2;:::)aredisjoint, then

P(

S

1

i=1 F

i )=

P

1

i=1 P(F

i ).

Now,letus onsidertherootedGRTS (S;AType;T;s

0

). Wedenefun tion

Pr : S A tS ! [0;1℄ by Pr(s;;s 0

) = P

fjpj(s;;p;s 0

) 2 Tjg and, for

C  S, Pr(s;;C) = P

s 0

2C

Pr(s;;s 0

). An exe ution fragment is a nite

sequen e  = s

0

1;p1

!s

1

2;p2

! :::s

k

, su h that (s

i 1

;

i

;p

i

;s

i

) 2 T for ea h

i2f1:::kg. Wedenote bytr()thesequen e 

1

;:::;

k

andwesaythat is

maximal ifand onlyifthe laststate s

k

of  isterminal. Moreover,wedenote

byPr()=Pr(s

0

;

1

;s

1

)
:::
Pr(s

k 1

;

k

;s

k

)theprobabilityoftheexe ution

fragment. Anexe utioniseitheramaximalexe utionfragmentoraninnite

sequen e  0

=s

0



1

;p

1

!s

1



2

;p

2

! ::: where (s

i 1

;

i

;p

i

;s

i

)2T forea h i2 IN.

In parti ular, we denote by tr

k (

0

) the sequen e 

1

;:::;

k

. Finally, let  "

denotethesetofexe utionsfj 0

j 

prex

 0

jgwhere

prex

istheusualprex

relationonsequen es.

Now, given an initial state s 2 S, we dene a probability spa e on the

exe utions whi h start in s. Let Exe (s) be the set of exe utions starting in

s andExe Frag(s) betheset ofexe ution fragmentsstarting in s. Wedenote

by (s) thesmallest sigmaeld on Exe (s)whi h ontainsall  "where  2

Exe Frag(s) . TheprobabilitymeasureProb istheuniquemeasureon(s)su h

that Prob(")=Pr().

By assuming C  G, P 2 G, and A  A t



, we denote by Exe (A;C)

theset of exe utionsthat leadto astate in C from theirinitial statethrough

a sequen e in A, i.e.  0

2 Exe (A;C), with  0

= s

0



1

;p

1

!s

1



2

;p

2

! :::, if and

only if there exists k su h that tr

k (

0

) belongs to the set of sequen es in A

and s

k

2 C. Let Exe (P;A;C) def

= Exe (A;C)\Exe (P). It is easy to see

that Exe (P;A;C)ismeasurablein (P), asExe (P;A;C)= S



",where 

rangesoverallexe ution fragmentsstarting in P whose last stateisin C and

tr()isasequen ein A.

Inthefollowing,



^

a standsforthesetof sequen es



aifa2GA t fg

andforthesetofsequen es



ifa=.

Theorem 4.1 Denotedwith Prob(P;



^

a;C) the probability of going from P

to aterminC viasequen esoftheform



^

a,theequationProb(P;



^ a;C)=

8

<

:

1 if a=^P 2C

P

Q2G

Prob(P;;Q)
Prob(Q;



;C) if a=^P 62C

P

Q2G

Prob(P;;Q)
Prob(Q;



a;C)+Prob(P;a;C) if a6=



thedenition of weak probabilisti bisimulationforfully probabilisti systems

of [7℄, where theweaktransition relation

^ a

) ofMilner [44℄ is repla edby the

probability Prob(P;



^

a;C). It is worth noting that the authors of [7℄ dene

bothweakanddelaybisimulation[44℄forfullyprobabilisti transitionsystems

and show that these two relations oin ide in theprobabilisti setting (hen e

we anuse



^

ainsteadof



^ a



inthefollowingdenition).

Denition4.2 An equivalen e relation R  GG is a weak probabilisti

bisimulationifandonlyif,whenever(P;Q)2R ,thenforallC2G=R :

 Prob(P;



^

a;C)=Prob(Q;



^

a;C) foralla2GA t

 Prob(P;a



;C)=Prob(Q;a



;C) foralla



2RA t

Two terms P;Q 2 G are weakly probabilisti ally bisimulation equivalent,

denotedP

PB

Q,ifthereexistsaprobabilisti weakbisimulationR ontaining

thepair(P;Q).

Notethatsin ethe hoi ebetweenrea tivea tionsandinternal(generative)

a tions is nondeterministi , then the denition aboverequires two equivalent

termstobestronglyequivalentin aseofrea tivea tions.

Example4.3 ThetwotermsP

=(a



:0+a:0)andQ

=(a



:0+:P)areweakly

probabilisti allybisimulationequivalent. Fromanexternalobserverstandpoint,

bothtermsnondeterministi ally hoosebetweenarea tivea tiona



andagen-

erativea tion a. LetR betheequivalen erelationonS =fP;Q;0gsu hthat

S=R=fC

1

;C

2

gwith C

1

=fP;QgandC

2

=f0g. Therefore,forea hS 0

inC

1

wehaveProb(S 0

;



a;C

2

)=1and Prob(S 0

;a



;C

2

)=1. Notethat,if weerro-

neouslytry torelax thestrong onditionin aseof rea tivea tions,wewould

obtain Prob(Q;



a



;C

2

) = 2, sin e Q has at his disposal twopossible paths

for the exe utionof a



, but the hoi e between these twopaths is ompletely

nondeterministi .

Example4.4 Let us onsider the two GRTSs of Fig. 7, whi h turn out to

be weakly probabilisti ally bisimulation equivalent. To show su h a result,

let R be the equivalen e relation on S = fS

0

;S

1

;S

2

;S 0

0

;S 0

1

;S 0

2

g su h that

S=R=fC

1

;C

2

gwhereC

1

=fS

0

;S 0

0

gistheequivalen e lassoftheinitialstates

and C

2

=fS

1

;S

2

;S 0

1

;S 0

2

gisthe equivalen e lass ofthe remainingstates. For

ea hS 0

2C

1

wehaveProb(S 0

;



;C

1

)=1 andProb(S 0

;



;C

2

)=1=2where

 2fa;bg. Ontheother hand,for ea h S 0

2C

2

wehaveProb(S 0

;



;C

2 )=1

and Prob(S 0

;



;C

1

)=0 where  2 fa;bg. Hen e, R is aweak probabilisti

bisimulation. ItisworthnotingthatfromstateS 0

0 2C

1

werea hstateS 0

1 2C

2

(S 0

2 2C

2

)viaana tiona(b)byexe utinganarbitrarynumberoftimesthea -

tion. InordertoevaluatetheprobabilityProb(S 0

0

;



a;C

2

)(Prob(S 0

0

;



b;C

2 ))

wehavetoredistributetheprobability 1

asso iatedwiththeoutgoinginternal

transitionofS

0

amongtheotheroutgoingtransitionsofS

0

. Byapplyingthefor-

muladenedinthisse tion,wehaveProb(S 0

0

;



a;C

2 )=

1

3

Prob(S 0

0

;



a;C

2 )+

1

3

fromwhi hweobtainProb(S 0

0

;



a;C

2 )=

1

2

(similarlyforb).

1/3

a b S’ 1 S’ ₂ a b

S ₁ S ₂

S ₀

1/2 1/2

S’ 0 ^1/3 1/3

τ

PB

Figure7: Bisimulationequivalentprobabilisti systems

Asfarastheequivalen e he kis on erned,[7℄des ribesanalgorithmthat

omputesweakprobabilisti bisimulationequivalen e lassesintimeO(n 3

)and

spa eO(n 2

),where nisthenumberofstates. Wenowshowthat iftwoterms

areweaklyprobabilisti allybisimulationequivalent,thentheirnondeterministi

ounterpartsareweaklybisimulationequivalent. Formally,thefollowinglemma

showsthat,giventwotermsP;Q2G su hthat P 

PB

Q,thenthetwoterms

P

nd

;Q

nd 2G

nd

obtainedfrom P andQbyremovingtheprobabilitiesfromthe

algebrai operatorsareweaklybisimulationequivalent.

Lemma4.5 GivenP;Q2G,P 

PB

Q)P

nd



B Q

nd .

In parti ular, as we will see in the next se tion, su h a result is used to

prove that the se urity properties dened in our probabilisti setting apture

allinformation owsthatarisebyanalyzingthenondeterministi behaviorofa

system.

We on ludethisse tionbygivinganotionofweakprobabilisti bisimulation

upto

PB

in thelineof[13℄,thatwillbeusedinthenextse tionin theproof

of Theorem5.11. Inthefollowingdenition,givenarelation R ,wedenote by

R 1

theinverserelationofR ,andby(R ) +

thetransitive losureofR .

Denition4.6 ArelationRGGisaweakprobabilisti bisimulationupto



PB

ifandonlyif,whenever(P;Q)2R ,thenforallC2G=(

PB

[R[R 1

) +

:

 Prob(P;



^

a;C)=Prob(Q;



^

a;C) foralla2GA t

 Prob(P;a



;C)=Prob(Q;a



;C) foralla



2RA t:

5 Se urity Properties for Probabilisti Pro esses

Inthisse tion,wepresentthreeprobabilisti se urityproperties,byextending

thenon-interferen etheorydes ribed inSe t. 2totheprobabilisti framework

wewanttoex ludethosetransitionsystemswheretheprobabilityofobserving

a visible event a (pre eded by a sequen e of invisible a tions) may tend to

0. This is possible, e.g., if the transition system enables exe ution fragments

 of the form 



a, where the sequen e of visited states is a y li and Pr()

tendsto 0asthelengthof thesequen e



tendsto 1. Ifthis isthe ase, we

annot quantify neither theprobability of observing thevisible event a, sin e

itsexe utionprobabilitymaytendto0,northeee t ofsu hapotentialevent

onthe (low-level)observablebehaviorofthesystem. In orderto avoidsu ha

situationandtosimplifythete hni alma hineryneededintherestofthepaper,

werestri tourselvestonitestatepro esses. Extensionswhi h in ludeinnite

pro essesare possible,but would ompli ateourdenitions and theorems. In

thefollowing,wedenotebyG f

thesetofnitestatepro essesand,bytakinginto

onsiderationsu h afamily, we introdu e theprobabilisti versionofthe non-

interferen epropertiesofSe t.2.2. Then,throughseveralexamples,wedis uss

su h properties by emphasizing their adequa y to reveal indire t information

owsthat are not aptured by lassi alproperties based on nondeterminism.

Afterwards,weshowthatourprobabilisti approa hisa onservativeextension

ofthenondeterministi approa htoinformation owtheorydes ribedinSe t.2.

Finally, weshowthat by modeling the probabilisti behavior of the systema

quantitativeestimateoftheinformation ow anbegiven,inthesensethatwe

anevaluatetheprobabilityofobservingea h(potentiallyinse ure)behavior.

5.1 Probabilisti Non-interferen e

Westartouranalysisbydening aprobabilisti extensionoftheBSNNI prop-

erty,thatwe all BisimulationStrongProbabilisti Non-interferen e(BSPNI).

Inthefollowing,givenP 2G f

,wedenotebyH

P

AType

H

theset ontaining

thetypesofthehigh-levela tionswhi hsynta ti allyo urinthea tionprex

operators within P, by h

P

the sequen e (in alphabeti order) of the typesin

H

P

, andbyjH

P

jthe ardinalityof H

P

. Moreover,wedenoteby Seq k

D theset

ofk-lengthsequen eswithdomainD.

Denition5.1 P 2G f

isBSPNI se ureifandonlyif

P=

p

h

P



PB

PnAType

H

8p2Seq jH

P j

℄0;1[

:

The intuition under su h a denition is that a system P is se ure if and

only if the probability distribution of the events whi h are observable by a

low user isindependent of the behavior of thehigh user. In other words, the

BSPNI property extends the ondition he ked by the BSNNI property by

takinginto onsiderationalsotheprobabilisti information. Note thatin term

P=

p

h

P

, the parameters p

1 :::p

jH

P j

forming the sequen e p are used to solve

thenondeterminisminP due tothepotentialintera tionofanyrea tivehigh-