Day 2.


82 views
Uploaded on:
Category: Sales / Marketing
Description
Day 2 The requirement unraveling calculation Layout Review of Lesson 1. The confirmation calculation. A worked sample. Comments. Section 1 Reviving the memory Sentence structure: Prolog-based terms. a, b, [A,b]*pk(A), … messages are terms variables: start with capitalized (or _) occasions send(t) recv(t)
Transcripts
Slide 1

Day 2 The imperative understanding calculation

Slide 2

Outline Recall of Lesson 1. The confirmation calculation. A worked case. Comments.

Slide 3

Part 1 Refreshing the memory

Slide 4

Syntax: Prolog-based terms. a, b, [A,b]*pk(A), … messages are terms variables: start with capitalized (or _) occasions send(t) recv(t)

Slide 5

Specifying a Protocol: Roles are arrangements of occasions. Variables are utilized as parameters. Parts of NS: initiator(A,B,Na,Nb) = [ send([A,Na]*pk(B)), recv([Na,Nb]*pk(A)), send(Nb*pk(B))]. responder(A,B,Na,Nb) = [ recv([A,Na]*pk(B)), send([Na,Nb]*pk(A)), recv(Nb*pk(B))]).

Slide 6

Scenarios Used to determine a session. E.g. {initiator(a,B,na,Nb), responder(A,b,Na,nb), {recv(nb)} } Scenarios permit to determine: what number of operators are available in a session for every specialists its name what he “knows” a (non)- mystery part, that can be utilized for checking mystery.

Slide 7

Originator Assumption When assembling a situation, verify that if an operators has a variable (say X) as parameter THEN in the specialists\' meaning X must happen first in a recv occasion. Review : initiator(A,B,Na,Nb) = [send([A,Na]*pk(B)),recv([Na,Nb]*pk(A)),send(Nb*pk(B))]. At that point, look at: {initiator(a,B,na,Nb), responder(A,b,Na,nb), {recv(nb)} } {initiator(a, b ,na,Nb), responder(A,b,Na,nb), {recv(nb)} } How would we be able to examine the first situation?

Slide 8

Solution Add a recv occasion in the part definition . New part definition initiator(A,B,Na,Nb)=[ recv(B), send([A,Na]*pk(B)), recv([Na,Nb]*pk(A)), send(Nb*pk(B))]. The situation {initiator(a,B,na,Nb), responder(A,b,Na,nb), {recv(nb)} } Not especially exquisite, however stable and successful.

Slide 9

Exercise Why is it essential: If the O.A. is not fulfilled: then the investigation\'s aftereffect can be wrong (all the more later) the hunt space could build drastically (crash dangers). Obviously numerous initiator(A,B,S,Na) = [recv([A,B]),send([A,Na]*pk(S))]. Choose if the accompanying situations fulfill O.A.: { initiator(a,B,s,na) } { initiator(a,B,s,Na) } { initiator(A,B,S,na) } { initiator(a,B,B,na) }

Slide 10

Solution yes no yes

Slide 11

Part 2 The Verification Algorithm And the imperative fathoming stuff

Slide 12

Preliminaries: Unification a substitution  is a mapping from variables to terms {X  a}, {X  Y, Y  a}  is a unifier of t and s iff t = s. e.g., p(X,a), q(r(Z),W), = {X  r(Z), W  a} or 2 = {X  r(b),W  a,Z  b}  is more broad than 2 two terms bind together in the event that they have a unifier then there exists a most broad unifier (mgu)

Slide 13

Constraints An imperative is a couple: m:T m is a message term, T is a rundown of terms. is called basic if m is a variable. natural significance: “ m is generable from T” The Constraint Store (CS) is an arrangement of imperatives.

Slide 14

the Verification Algorithm S: situation CS: limitation store (at first exhaust) K: intruder’s learning. A confirmation\'s stage calculation: pick the first occasion e from a non-exhaust part of S case 1) e = send(t) K := K U {t}; continue case 2) e = recv(t) CS := CS U {t:K } if CS can be tackled to CS’ with arrangement  , S := S ; K:= K ; CS := CS’; continue generally, stop

Slide 15

What is resolvable? CS can be understood to CS’ with arrangement  on the off chance that we can apply diminishment tenets to CS until we acquire CS’, where CS’ is void or CS’ contains just basic limitations.

Slide 16

Synthesis lessening standards   :modifying step yielding substitution   is the void substitution Local guidelines: Pair: [m1,m2]:T   m1:T , m2:T hash: h(m):T   m:T penc: m*pk(a) :T   m:T, a:T senc: m+k :T   m:T, k:T sig: m*sk(e)   m:T Global principle bring together: {m:T,C1,…,Cn}   {C1,…,Cn} gave that =mgu(m,t), tT

Slide 17

Analysis diminishment rules (2) Affect the opposite side of the limitation. Neighborhood tenets split: m:{[t1,t2]}  T   m:{t1,t2} T pdec: m:{t*pk(e)}  :T   m:{t}  T sdec: m:T{t+k}   k:T{t-k}, m:T{t,k} disregard this one utilized just for built symmetric keys Global principle ksub: {m:{t*k}T, C1, …, Cn}   {m:({t*k}T), C1, …, Cn} where =mgu(k,pk(e)), kpk(e)

Slide 18

the Result CS0  1 CS1  2 …  n CSn every time a requirement in CS is chosen and a guideline is connected to it The revising stops when CSn is void or made of straightforward imperatives CS is illuminated the substitutions\' creation is the rearrangements\' aftereffect:  := 1 2 … n a limitation is chosen that can\'t be streamlined CS is unsolvable there is no outcome (disappointment)

Slide 19

Properties Is it Confluent? No. Diverse decrease successions are conceivable: altogether: 4 wellsprings of nondeterminism decision of the occasion in the calculation. decision of the limitation to be decreased. decision of the guideline to be connected. in the examination rules and in the bind together manage there is the extra decision of the term in T to which the principle is connected. Full backtracking to protect fulfillment. Nearby investigation decrease principles save conjunction, and this can be utilized for streamlining.

Slide 20

Part 3 Example

Slide 21

Example Consider the situation for NS with OA: { initiator(a,B,na,Nb), responder(A,b,Na,nb) , {recv(nb)} } A conceivable interleaving: recv([A,B]), send([a,na]*pk(B)) recv([A,Na]*pk(b)), send([Na,nb]*pk(A)) recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... We overlook the occasions after recv(nb)

Slide 22

Example (cont) recv([A,B]), send([a,na]*pk(B)) recv([A,Na]*pk(b)), send([Na,nb]*pk(A)) recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... figure out what happens to the CS T = {a,b,e} (interloper information) CS = {}

Slide 23

The run (1) recv([A,B]), send([a,na]*pk(B)), recv([A,Na]*pk(b)), send([Na,nb]*pk(A)), recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... Prior to the stride T = {a,b,e} CS = {} After (T does not change) CS = {[A,B]:{a,b,e}} By applying pair CS’ = {A:{a,b,e}, B:{a,b,e}}

Slide 24

The run (2) send([a,na]*pk(B)), recv([A,Na]*pk(b)), send([Na,nb]*pk(A)), recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... Prior to the stride T = T0 = {a,b,e} CS = {A:{a,b,e}, B:{a,b,e}} After T = T1 = {a,b,e,[a,na]*pk(B)}

Slide 25

The run (3) recv([A,Na]*pk(b)), send([Na,nb]*pk(A)), recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... Prior to the stride T = T1 = {a,b,e,[a,na]*pk(B)} (T0 = {a,b,e}) CS = {A:{a,b,e}, B:{a,b,e}} After CS = {A:T0, B:T0, [A,Na]*pk(b):T1} by penc + pair CS = {A:T0, B:T0, A:T1, Na:T1, b:T1} by nif CS = {A:T0, B:T0, A:T1, Na:T1}

Slide 26

The run (4) send([Na,nb]*pk(A)), recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... Prior to the stride T = T1 = {a,b,e,[a,na]*pk(B)} T0 = {a,b,e} CS = {A:T0, B:T0, A:T1, Na:T1} After T = T2 = T1 U {[Na,nb]*pk(A) T1 = {a,b,e,[a,na]*pk(B)} T0 = {a,b,e} CS is unaltered

Slide 27

The run (5) recv( [na,Nb]*pk(a)), send([Nb]*pk(B)), recv(nb) ... Before T = T2 = T1 U {[Na,nb]*pk(A) T1 = {a,b,e,[a,na]*pk(B)} T0 = {a,b,e} CS = {A:T0, B:T0, A:T1, Na:T1} After CS= {A:T0, B:T0, A:T1, Na:T1,[na,Nb]*pk(a):T2} bring together! (Na-> na , Nb - > nb and A-> a) The unification must be connected to the rest…

Slide 28

The run (5.1) recv([na ,b]* pk(a)), send ([nb]* pk(B)), recv(nb) ... After the unification: T = T2 = T1 U {[ na, nb]*pk (a) T1 = {a,b,e,[a,na]*pk(B)} T0 = {a,b,e} CS= { a :T0, B:T0, a :T1, na :T1} Unify CS= {B:{a,b,e}, na : {a,b,e,[a,na]*pk(B)}}

Slide 29

The run (5.2) recv([na,b]*pk(a)), send([nb]*pk( e )), recv(nb) ... After the unification: CS= {B:{a,b,e}, na : {a,b,e,[a,na]*pk(B)}} ksub (unification B - > e) + split CS= { e :{a,b,e}, na : {a,b,e,a,na}} bring together twice, with vacant answer CS = {} T = {[na,nb]*pk(a), a,b,e,[a,na]*pk( e )}

Slide 30

The run (5.3) send([nb]*pk( e )), recv(nb) ... Before CS = {} T = {[na,nb]*pk(a), a,b,e,[a,na]*pk(e)} After CS = {} T = {[na,nb]*pk(a), a,b,e,[a,na]*pk(e), [nb]*pk(e)}

Slide 31

The run (5.4) recv(nb) ... Before CS = {} T = {[na,nb]*pk(a), a,b,e,[a,na]*pk(e), [nb]*pk(e)} After CS = {nb:{[na,nb]*pk(a), a,b,e,[a,na]*pk(e), [nb]*pk(e)}} pdec CS = {nb:{[na,nb]*pk(a), a,b,e,[a,na]*pk(e),nb}} bind together (discharge substitution) CS = {} !!!

Slide 32

The arrangement substitution We wound up with an unfilled CS => the framework has an answer all the while, decrease principles gave us the `solution substitution’  = {A->a,Na->na,Nb->b, B->e}

Slide 33

Part 3 Considerations

Slide 34

Again, the O.A. Consider two parts: roleA(X) = { send(X) } roleB(Nb) = { recv(Nb) } and situation { roleA(X), roleB(nb) } interloper learning: {a,b,e} imperatives produced: nb : {X} feasible, by tenet (bind together) this is not what we need!

Slide 35

Laziness We quit rearranging a requirement when the lhs is a variable. This upholds a call-by-need instrument. The length of the lhs is a variable the requirement is inconsequentially reasonable. In the event that resulting unification step instantiate the lhs of a requirement, then I check further on the off chance that it can be explained. It is senseless to figure.

Slide 36

Another Example for Laziness Consider two parts: roleA(X,A) = { recv(X), recv(X*pk(A)) } roleB(Na,A) = { send(Na*pk(A)) } and this scenario:{roleA(X, b), roleB(na,b)} introductory gatecras

Recommended
View more...