doc-src/TutorialI/Protocol/document/Event.tex
changeset 40406 313a24b66a8d
parent 23925 ee98c2528a8f
equal deleted inserted replaced
40405:42671298f037 40406:313a24b66a8d
   464 \begin{isamarkuptext}%
   464 \begin{isamarkuptext}%
   465 The system's behaviour is formalized as a set of traces of
   465 The system's behaviour is formalized as a set of traces of
   466 \emph{events}.  The most important event, \isa{Says\ A\ B\ X}, expresses
   466 \emph{events}.  The most important event, \isa{Says\ A\ B\ X}, expresses
   467 $A\to B : X$, which is the attempt by~$A$ to send~$B$ the message~$X$.
   467 $A\to B : X$, which is the attempt by~$A$ to send~$B$ the message~$X$.
   468 A trace is simply a list, constructed in reverse
   468 A trace is simply a list, constructed in reverse
   469 using~\isa{{\isacharhash}}.  Other event types include reception of messages (when
   469 using~\isa{{\isaliteral{23}{\isacharhash}}}.  Other event types include reception of messages (when
   470 we want to make it explicit) and an agent's storing a fact.
   470 we want to make it explicit) and an agent's storing a fact.
   471 
   471 
   472 Sometimes the protocol requires an agent to generate a new nonce. The
   472 Sometimes the protocol requires an agent to generate a new nonce. The
   473 probability that a 20-byte random number has appeared before is effectively
   473 probability that a 20-byte random number has appeared before is effectively
   474 zero.  To formalize this important property, the set \isa{used\ evs}
   474 zero.  To formalize this important property, the set \isa{used\ evs}
   475 denotes the set of all items mentioned in the trace~\isa{evs}.
   475 denotes the set of all items mentioned in the trace~\isa{evs}.
   476 The function \isa{used} has a straightforward
   476 The function \isa{used} has a straightforward
   477 recursive definition.  Here is the case for \isa{Says} event:
   477 recursive definition.  Here is the case for \isa{Says} event:
   478 \begin{isabelle}%
   478 \begin{isabelle}%
   479 \ \ \ \ \ used\ {\isacharparenleft}Says\ A\ B\ X\ {\isacharhash}\ evs{\isacharparenright}\ {\isacharequal}\ parts\ {\isacharbraceleft}X{\isacharbraceright}\ {\isasymunion}\ used\ evs%
   479 \ \ \ \ \ used\ {\isaliteral{28}{\isacharparenleft}}Says\ A\ B\ X\ {\isaliteral{23}{\isacharhash}}\ evs{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ parts\ {\isaliteral{7B}{\isacharbraceleft}}X{\isaliteral{7D}{\isacharbraceright}}\ {\isaliteral{5C3C756E696F6E3E}{\isasymunion}}\ used\ evs%
   480 \end{isabelle}
   480 \end{isabelle}
   481 
   481 
   482 The function \isa{knows} formalizes an agent's knowledge.  Mostly we only
   482 The function \isa{knows} formalizes an agent's knowledge.  Mostly we only
   483 care about the spy's knowledge, and \isa{knows\ Spy\ evs} is the set of items
   483 care about the spy's knowledge, and \isa{knows\ Spy\ evs} is the set of items
   484 available to the spy in the trace~\isa{evs}.  Already in the empty trace,
   484 available to the spy in the trace~\isa{evs}.  Already in the empty trace,
   485 the spy starts with some secrets at his disposal, such as the private keys
   485 the spy starts with some secrets at his disposal, such as the private keys
   486 of compromised users.  After each \isa{Says} event, the spy learns the
   486 of compromised users.  After each \isa{Says} event, the spy learns the
   487 message that was sent:
   487 message that was sent:
   488 \begin{isabelle}%
   488 \begin{isabelle}%
   489 \ \ \ \ \ knows\ Spy\ {\isacharparenleft}Says\ A\ B\ X\ {\isacharhash}\ evs{\isacharparenright}\ {\isacharequal}\ insert\ X\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}%
   489 \ \ \ \ \ knows\ Spy\ {\isaliteral{28}{\isacharparenleft}}Says\ A\ B\ X\ {\isaliteral{23}{\isacharhash}}\ evs{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ insert\ X\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}%
   490 \end{isabelle}
   490 \end{isabelle}
   491 Combinations of functions express other important
   491 Combinations of functions express other important
   492 sets of messages derived from~\isa{evs}:
   492 sets of messages derived from~\isa{evs}:
   493 \begin{itemize}
   493 \begin{itemize}
   494 \item \isa{analz\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}} is everything that the spy could
   494 \item \isa{analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}} is everything that the spy could
   495 learn by decryption
   495 learn by decryption
   496 \item \isa{synth\ {\isacharparenleft}analz\ {\isacharparenleft}knows\ Spy\ evs{\isacharparenright}{\isacharparenright}} is everything that the spy
   496 \item \isa{synth\ {\isaliteral{28}{\isacharparenleft}}analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}} is everything that the spy
   497 could generate
   497 could generate
   498 \end{itemize}%
   498 \end{itemize}%
   499 \end{isamarkuptext}%
   499 \end{isamarkuptext}%
   500 \isamarkuptrue%
   500 \isamarkuptrue%
   501 %
   501 %