l:=rand(1)
wherehisahigh-levelvariablethathasbeenpreviouslyseteitherto0orto1by
thehigh user(e.g., a ordingtoagivenprobabilitydistribution), andrand(n)
is afun tion whi h randomly samplesa naturalnumberin the set f0;:::;ng.
Then, thelow-level output(i.e. the value of variable l) either is dire tly read
by the high-level output with probability p oris randomly sampled from the
possiblevalues0and1withprobability1 p. Thebehaviorofsu hasystemis
graphi allyrepresentedinFig.10. Itiseasytoseethattheaboveprogramhas
noinformation owifweonly onsiderthepossiblebehaviorsofthesystem,but
the nal valueof lwill revealhif thelowuser observestherelativefrequen y
ofout omesofrepeatedexe utions.
H
L
l rand
h
choice prob.
Figure10: Exampleofasystem on ealingaprobabilisti overt hannel
Similarly,letus onsiderthefollowingpro ess:
P
=(l
0 :P+
1
2
l
1 :P)+
p
h:(l
0 :P+
q
l
1 :P)
wherealowuserobserveseitherana tionl
0
orana tionl
1
withaprobability
distribution that depends on the high environment behavior. In parti ular, if
no external ommuni ation an be ompleted via a syn hronization with the
high a tion h, thesystem hooses betweenthe twolow-levela tions l
0 andl
1
withthesameprobability 1
2
(su ha hoi emodelstheassignmentl:=rand(1)).
Ontheotherhand,ifthesystemintera tswiththehighuserbyexe utingthe
a tionh,thentheprobabilitydistributionofthetwolow-leveleventsisguided
byparameterq(su ha omponentisthe ounterpartoftheassignmentl:=h).
values (0 and 1) that h an assume and transmit to the low part, while p is
theparameterwhi hguidestheprobabilisti hoi ebetweenthetwoalternative
waysofprodu ing alow-leveloutput. Thenondeterministi versionof pro ess
P isse ure,be ausethehighbehaviordoesnotalterthelowviewofthesystem,
that isrepresentedby anondeterministi hoi ebetweenthea tionsl
0 andl
1 .
However,intheprobabilisti settingthisisnotthe ase. Indeed,theprobability
ofobservingana tionl
0
withrespe ttoana tionl
1
hangesdependingonthe
behaviorof thehigh user. Inparti ular, from PnAType
H
(see Fig.11). Inpra ti e, wehavethat
P isBSPNI se ure ifand only ifq = 1
2
, be ausein su h a ase thehigh user
simulatesthebehaviorofthefun tionrand(1)usedtodeterminethelowoutput,
sothat alowuser annotinferthehigh behaviorby observingtheprobability
distributionofthetwolow-levela tions.
p 2
Figure11: S
0
Theinformation owinExample5.5isnot apturedbyanyse urityproperty
de nedin [25℄,sin ethepotentialintera tionbetweenthesystemandthehigh
userdoesnot hangethepossibilisti behaviorthat isobservablebyalowuser.
In other words, the overt hannel of Example 5.5 is merely probabilisti , in
that itisrevealedbyobservingthelow-levelprobabilisti behavioronly.
5.2 Probabilisti Nondedu ibility On Composition
Sometimesthenon-interferen epropertyisnotenoughto aptureallthe
poten-tialinse urebehaviorsofasystem. Forthisreason,otherpropertieshavebeen
suggestedinordertoover omethela ksofsu haproperty. Amongthedi erent
proposals,herewe onsidertheBNDC that,inourprobabilisti setting,we all
Probabilisti BNDC (PBNDC,forshort).
De nition5.6 P 2G f
isPBNDC se ureifandonlyif
PnAType
ofhigh-leveltypes,82G f
;8p2℄0;1[and8p2Seq k
℄0;1[
.
respe t to the exe ution of P in parallel with any high-level pro ess . The
PBNDC does not depend on the probability distribution of the hidden
high-levela tionswhi hderivefromthesyn hronizationsbetweenP and,be ause
itistobesatis ed:
for any hoi e of pro ess whi h guides the probability distribution of
thegenerative high-level a tions whi h areo ered by the high user and
syn hronizewiththe orrespondingrea tivehigh-levela tionsofP,
forany hoi eofparametersp
1
;:::;p
k
formingthesequen ep,whi hare
hosenbythehigh userto solvethenondeterminismdue to therea tive
high-level a tions exe utable by Pk p
fh1;:::;h
k g
(deriving from
syn hro-nizationsamongrea tivehigh-levela tionsofthesametypeofP and)
thatareturnedintointernal a tions,
forany hoi eofparameterp,whi hguidestheprobabilisti parallel
exe- utionofpro essesP and .
The PBNDC property expresses an intuition similar as that underlying the
notion of probabilisti non-interferen e given by Gray in [32℄. In parti ular,
Grayde nesthenotionsofhigh environmentbehavior Handlow environment
behavior L, whi h give the probability of the external environmentprodu ing
high (low)inputsgiventhat theprevioushistoryofhigh (low)inputand
out-put eventshas takenpla e. Then, he he ksif, by xing L and bymodifying
H , the probability distribution of the low-level events of the system hanges
ornotdepending onthe environmentbehaviordes ribed byL and H . Inour
pro ess-algebrai framework,Lis xed(notethatP is onstrainedto
syn hro-nizeonhigh-levela tionsonly,meaningthatthelowenvironmentbehaviordoes
notalterthe probabilitydistribution of thelow-levela tions ofP),while His
expli itly modeled by the high-level pro ess , that intera ts with the
rea -tivehigh-level(input) a tionsandthegenerativehigh-level(output) a tionsof
P. Then, we he kifanyhigh userisableto a e tthe probabilisti lowview
of P, or, by using the terminology borrowedfrom Gray, we he k if thehigh
environmentbehavioralterstheprobabilitydistributionofthelow-levelevents.
As in the nondeterministi framework, PBNDC is at least as strong as
BSPNI.
Proposition5.7 PBNDCBSPNI.
Theexample reported in the proof of Proposition 5.7 (P
=l:0+ p
h:h:l:0)
showsthatthe BSPNI propertyis notableto dete tsomepotentialdeadlo k
duetohigh-levela tivities,exa tlyasshownin[24℄inthenondeterministi ase.
Similarly,thenextexamplerevealsthatthePBNDC ismoreadequatethanthe
BSPNI to aptureprobabilisti overt hannels.
P
whose orresponding GRTS is shown in Fig. 12(a). It is provable that P 2
BSPNI. Indeed,wehavethatP=AType
H
Intuitively, it is easy to see that if a low user observesthe a tion l, then
heknowsthat thehigh-levela tion h
1
hasnottakenpla e. Morepre isely, to
showthepotential overt hannel whi h may be set upfrom highlevelto low
level, we observethat a high user may(i) prevent the exe utionof a tion h
2
of the omponenth
2
:l:0,(ii) wait for theprobabilisti hoi e betweenthetwo
internala tions ,andthen(iii)ifthe rst omponentl:0+ p
h
1
:0is hosenwith
probability1 p,he ana e t the lowview ofthe systemby ommuni ating
(ornot)thea tionh
1
. We anprovethat thisinse urebehavioris apturedby
thePBNDC property. Tothisend, onsiderthepro ess
=h
1
:0andthe
syn- hronization setS =fh
1
isdepi tedinFig.12(b). Inparti ular,thebehaviorofsu ha omposedsystem
onsistsofaprobabilisti hoi ebetweenthea tionl,performedwith
probabil-ityp,andtheinternal a tion , performedwithprobability1 p. The GRTS
derivedfromP=AType
H
isthatofFig.12( ),whi his learlynotequivalentto
that ofFig.12(b). Therefore,((Pk
S
onsequen e,P isnotPBNDC se ure.
p
Figure12: ExampleofasystemthatisBSPNI se urebut notPBNDC se ure
Finally, itis worthnotingthat, similarly asreported in [24,26℄, theabove
de nition of PBNDC is diÆ ultto usebe auseof theuniversalquanti ation
onhigh-levelpro esses. Forthisreason,in thefollowingse tionweproposethe
probabilisti versionoftheSBNDC propertythatsolvessu haproblem.
5.3 Strong Probabilisti BNDC
Inthisse tion,weintrodu eaprobabilisti se uritypropertystrongerthanthe
Example5.9 Thepro essP = :( :l
1 :0+
p
h:l
2 :0)+
p
:(h:l
1 :0+
p
:l
2
:0)
prob-abilisti allyevolveseither into astatewhi h performsa tion l
1
with
probabil-ity 1 orinto astate whi h performs a tion l
2
with probability 1. The
orre-spondingGRTS isshown inFig.13. Su hasystemisBSPNI se ure,be ause
P=AType
H
PB
:l
1 :0+
p
:l
2 :0
PB
PnAType
H
. Moreover,itisprovablethat
P is PBNDC se ure too. As a sket h of su h a proof, we observe that any
omposed term ((Pk q
S
)=S)nAType
H
is weakly probabilisti ally bisimulation
equivalentto:
P=AType
H
inthe aseh2S and enablesh,
PnAType
H
otherwise.
Should we onsider P asa se ure system? Intuitively, if we assumethat the
highuserisallowedtoknowwhetherfromtheinitialstateP thesystemevolves
either into P
1
or into P
2
(see Fig. 13), then the system is ertainly inse ure.
Indeed, the relativefrequen y of the low-level a tion l
1 (l
2
) asobserved in a
repeatedexe utionofsystemP in isolationisp(1 p), butsu h aprobability
distribution anbeeasilyalteredbyahighuserwho,awareofhowtheinternal
probabilisti hoi eintermP isresolved, ande idetoblo k(to ommuni ate)
thea tionh. Su habehaviorisnot apturedbythePBNDC,thereforeweneed
astronger notionof se urity, and to this end weintrodu ethe strong version
of the PBNDC. However, we point out that the assumption above on the
knowledgeofthehighuserwhi hisne essarytosetuptheinse ureinformation
owis, inourview,ratherquestionable.
1−p
τ, p
τ, p τ, 1−p
p τ, 1−p P
h,
P 1 P 2
h,
l 2 l 1 l 2 l 1
Figure 13: Exampleofa overt hannelinasystemthatis PBNDC se ure
Now,wede netheprobabilisti versionof theSBNDC thatwe allStrong
PBNDC (SPBNDC). Su hade nition ompletestheprobabilisti extensionof
thenondeterministi approa hpresentedinSe t. 2.
De nition5.10 P 2G f
is SPBNDC se ure ifandonlyif8P 0
2Der(P)and
8P 00
su hthat P 0
;p
!P 00
; t()2AType ;p2℄0;1℄;then
P nAType
H
PB
P nAType
H :
Ingeneral,byfollowingabasi intuitionsimilartothatgivenforAFMs[32℄,
an interpretation of the SPBNDC property is that in ea h system state the
probabilityoftheloweventsisindependentoftheprevioushighevents. Indeed,
supposed thattheprobabilitydistributionofaloweventlinagivenstateofa
systemP dependsonahigh a tionhpreviouslyexe uted,weshouldalsohave
that there exist P 0
and P 00
, rea hablefrom P, su h that P 0
h
!P 00
and the
probabilitydistributionoflinP 0
isnotequaltotheprobabilitydistribution of
linP 00
,thusviolatingtheSPBNDC property. Therefore,thestrong ondition
veri edbytheSPBNDC isthat inanystateofthesystemthelowuser annot
makeinferen es about high information previously ommuni atedby (to) the
high user. Theseveralexamples we reported in the previousse tions suggest
that, if we are interested in guaranteeing that what the low part an see is
independentofwhatthehighpart ando,thenthePBNDC istheappropriate
de nition with respe t toprote tionagainst probabilisti overt hannels. On
theotherhand,theSPBNDC iseasierto beveri edthanthePBNDC and,as
we ansee in the following Theorem 5.11, is also strongerthan the PBNDC.
Hen e,it anbeused asaveri ation onditionforPBNDC.
Theorem5.11 SPBNDC PBNDC.
Here,wejust giveanintuitionofthereasonwhythein lusionaboveholds.
IfasystemP isSPBNDC,thenP 0
!P 00
, withP 0
andP 00
derivativesofP
andt()2AType
H
,impliesthatP 0
nAType
H andP
00
nAType
H
areweakly
prob-abilisti allybisimulationequivalent. Therefore, theprobability distribution of
thehigh-levela tionsexe utablebyP 0
2Der(P)doesnota e ttheprobability
distributionofthelowviewofthesystem,or,equivalently,anyhigh-level
pro- essintera tingwithP 0
annotaltertheprobabilitydistributionofthelow-level
a tionsasobservedbyalowuser.
From the proof of Theorem 5.11, we derive that if P 2 SPBNDC then
8P 0
2 Der(P):P 0
nAType
H
PB ((P
0
k p
fh1;:::;hkg
)=
q
h1:::h
k
)nAType
H
, for ea h
sequen e h
1 :::h
k
of high-level types, 82 G f
H
, 8p 2℄0;1[, and 8q 2 Seq k
℄0;1[
.
Therefore,8P 0
2Der(P)wehavethatP 0
isPBNDC (andalsoBSPNI),whi h
isa onditionstri terthanthatwewantedtoprove.
5.4 Conservative Extension and Comparison
Inthisse tion,weshowthatthese uritypropertiesde nedinourprobabilisti
framework are the natural, onservativeextension of thepossibilisti se urity
properties based on the nondeterministi setting des ribed in Se t. 2.
Intu-itively, the integrationof probabilities asafurther aspe t of thesystemto be
deterministi ase. In the previous se tions, we have shown through several
examplesthatifanondeterministi modelP
nd
satis esase urityproperty,say
SP
nd
, then its probabilisti version P, obtained by modeling also the
proba-bilisti behaviorofthesystem,maynotsatisfythese uritypropertySP,whi h
is theprobabilisti ounterpartof SP
nd
. Now,wewantto showthatgivenan
arbitraryse uritypropertySP whi hhastobe he kedforatermP 2G f
,ifP
satis esSP thenP
nd
satis esSP
nd
. Inordertoprovesu h arelation,wenow
showwhat happens, from these urity propertyviewpoint, whenpassingfrom
theprobabilisti frameworktothenondeterministi one.
Thefollowingtheorem showsthat theprobabilisti se urity properties
ex-tend in the expe ted waythe orresponding nondeterministi ounterparts,in
the sense that if a probabilisti system turns out to be SP{se ure, then its
nondeterministi version obtained by repla ing probabilities by
nondetermin-isti hoi es is SP
nd
{se ure. Weassume SP 2 fBSPNI;PBNDC;SPBNDCg,
and we denote by SP
nd
the nondeterministi ounterpart of the probabilisti
propertySP, i.e.SP
nd
2fBSNNI;BNDC;SBNDCg.
Theorem5.12 (ConservativeExtension)
GivenP 2G f
,P isSP se ure)P
nd isSP
nd
se ure.
ByProposition5.7andTheorem5.11itfollowsthattheprobabilisti
exten-sionofthese uritypropertiespreservesthesamein lusionrelationshipsseenin
thenondeterministi aseinProposition2.10. Furtherpotentialrelationsamong
nondeterministi andprobabilisti se uritypropertiesaredis ussedthroughthe
followingexample.
Example5.13 Thenondeterministi systemP
nd
= :l:0+h
1
:l:0+ :0+h
2 :0
is BSNNI (P
nd
=AType
H
B
:l:0+ :0 iso
= P
nd nAType
H
) and, asit is easy to
verify,BNDC se ure. However,the exe ution ofthe low-level a tionl reveals
thatthehighuserhasnotperformedana tionoftypeh
2
. Su haninformation
owis aptured bytheSBNDC propertyonly.
Theprobabilisti extensionP
=( :l:0+ p
h
1 :l:0)+
1 p
( :0+ p
h
2
:0)isBSPNI
se ure. Indeed,wehave P=AType
H
PB
:l:0+ 1 p
:0
PB
PnAType
H . For
thesamereasonreportedin aseofP
nd
,termP shouldbe onsideredinse ure.
With respe t to the nondeterministi ase, where the SBNDC is needed to
revealtheinse urebehavior,inourprobabilisti settingthePBNDC isenough
to apture an information ow in P. Indeed, if we onsider the pro ess
=
h
2
:0andthesyn hronizationsetS=fh
1
;h
2
g,itfollowsthatP=AType
H 6
PB
((Pk
S
)=S)nAType
H .
TheexampleaboveshowsthattheBSPNI propertyisnotstri terthanthe
SBNDC property, i.e. even if a system P
nd
is notSBNDC se ure, its
proba-P =l:0+ p
h:h:l:0isBSPNI se ure(seetheproofofProposition 5.7),whileits
nondeterministi versionP
nd
=l:0+h:h:l:0doesnotsatisfytheBNDC
prop-erty (see Example 2.5). Therefore, the BSPNI property is not stri ter than
the BNDC property. In addition, Example 5.9 shows a pro ess P whi h is
PBNDC se ure, but notSPBNDC se ure. As it is easy to verify, its
nonde-terministi ounterpartP
nd
isBNDC se ure, but not SBNDC se ure. Hen e,
thePBNDC propertyisnotstri terthantheSBNDC property. This on ludes
thedis ussiononthein lusion relationsamongse urityproperties. InTable4
we graphi ally report the relations between the nondeterministi setting and
theprobabilisti one. The gureshows,e.g., thatif P 2G f
is BSPNI se ure,
then its nondeterministi version P
nd 2 G
nd
may benot BNDC se ure, sin e
theBSPNI labeledgraphisnotin ludedintheBNDC labeledgraph. Table4
reportsalsoalegendwithsomeexamplesrelatedtothedi erentregionsofthe
gure. Notethatwearenotawareofapro essP su hthatP isBSPNI se ure
and P
nd
is SBNDC se ure, but P isnot PBNDC (SPBNDC)se ure. If su h
a pro ess does notexist, then we would havean alternative, easily veri able
hara terizationofPBNDC.
PBNDC
BNDC BSPNI
SBNDC
BSNNI SPBNDC
1 2
3 4
5
6
7
Someexamples:
1: ( :(l:0+ 0:5
h
1 :0)+
0:5
:(l:0+ 0:5
:0))+ 0:3
h
2 :l:0
2: example5:8
3: example5:4
4: example5:13
5: example5:9
6: example5:5
7: example5:2
Table4: In lusionrelationshipamongse urityproperties
thestrongversionoftheBNDC turns outto beimportantto reveal potential
behaviors whi h are learly inse ure(see,e.g., Examples2.8 and2.9). Onthe
otherhand,inourviewintheprobabilisti aseitisnoteasyto ndarealisti
exampleshowingthattheSPBNDC isstrongerthanthePBNDC,whi hseems
tobetheadequatenotionofse urityinmost ases. Forinstan e,Example 5.9
assumesaverystrongknowledgeofthehighuser,whoshouldbeabletoseethe
result of an internal probabilisti hoi e within the systemto set up a overt
hannelwhi his aptured bytheSPBNDC, butnotbythePBNDC.
5.5 Interplay between Se urity and Probability
By modeling the probabilisti behavior of systems, new aspe ts of potential
information owsfrom high levelto low level anbeanalyzed. In parti ular,
whileinanondeterministi ,qualitativeviewwe anjustdedu ethatasystemis
orisnotse ure,intheprobabilisti settingwe anaddthatthesystemreveals
aninse ureinformation owwitha ertainprobability. A tually,the apa ityof
overt hannelsmaybemeasuredinanondeterministi settinginthesensethat
theamountofleakedinformation hangesa ordingto thenumberofdi erent
behaviors of the high user that anbe distinguished by alow user (see, e.g.,
[39℄). Here, our laim is that probabilisti information o ers the means for
evaluatingthereale e tivenessofea hofsu h unwantedbehaviors.
Fromapra ti alstandpoint,aquantitative,probabilisti approa hto
infor-mation owanalysis anbeusedtoverifythese uritylevelofsystemsforwhi h
probabilitiesplayanimportantrole. Forinstan e,manyproblems anbesolved
byusingdeterministi algorithmswhi hturnouttobese ureandrequire
expo-nentialtime. Ontheotherhand,probabilisti algorithmsareoftenimplemented
that solvethesameproblemsinpolynomialtime(see,e.g.,[15,41℄). Insu ha
ase,thepri etopayfora omputationalgainisthepossibilityfortheobserver
of dete tinganundesirableinformation ow. Be ause ofsu hapossibility, by
followinganapproa htoinformation owtheoryfornondeterministi pro esses,
the probabilisti algorithms turn out to beinse ure. Instead, by employinga
probabilisti approa h, we ouldformallyprovethat thesamealgorithmshave
aninse urebehaviorwhi hisexe utedwithprobability0(or loseto0). Hen e,
aformalquantitativeestimateoftheunwantedbehaviorsisde isivetoevaluate
the se urity level of probabilisti systems. To this end, answers to questions
like \What is the probabilitythat aninformation ow from high levelto low
level has taken pla e?" annot be provided if the veri ation of the se urity
propertiesonlydependson lassi albehavioralequivalen esliketheweak
propertiesonlydependson lassi albehavioralequivalen esliketheweak