src/HOL/SET_Protocol/Event_SET.thy
author wenzelm
Sat Jul 18 22:58:50 2015 +0200 (2015-07-18)
changeset 60758 d8d85a8172b5
parent 60754 02924903a6fd
child 63167 0909deb8059b
permissions -rw-r--r--
isabelle update_cartouches;
     1 (*  Title:      HOL/SET_Protocol/Event_SET.thy
     2     Author:     Giampaolo Bella
     3     Author:     Fabio Massacci
     4     Author:     Lawrence C Paulson
     5 *)
     6 
     7 section{*Theory of Events for SET*}
     8 
     9 theory Event_SET
    10 imports Message_SET
    11 begin
    12 
    13 text{*The Root Certification Authority*}
    14 abbreviation "RCA == CA 0"
    15 
    16 
    17 text{*Message events*}
    18 datatype
    19   event = Says  agent agent msg
    20         | Gets  agent       msg
    21         | Notes agent       msg
    22 
    23 
    24 text{*compromised agents: keys known, Notes visible*}
    25 consts bad :: "agent set"
    26 
    27 text{*Spy has access to his own key for spoof messages, but RCA is secure*}
    28 specification (bad)
    29   Spy_in_bad     [iff]: "Spy \<in> bad"
    30   RCA_not_bad [iff]: "RCA \<notin> bad"
    31     by (rule exI [of _ "{Spy}"], simp)
    32 
    33 
    34 subsection{*Agents' Knowledge*}
    35 
    36 consts  (*Initial states of agents -- parameter of the construction*)
    37   initState :: "agent => msg set"
    38 
    39 (* Message reception does not extend spy's knowledge because of
    40    reception invariant enforced by Reception rule in protocol definition*)
    41 primrec knows :: "[agent, event list] => msg set"
    42 where
    43   knows_Nil:
    44     "knows A [] = initState A"
    45 | knows_Cons:
    46     "knows A (ev # evs) =
    47        (if A = Spy then
    48         (case ev of
    49            Says A' B X => insert X (knows Spy evs)
    50          | Gets A' X => knows Spy evs
    51          | Notes A' X  =>
    52              if A' \<in> bad then insert X (knows Spy evs) else knows Spy evs)
    53         else
    54         (case ev of
    55            Says A' B X =>
    56              if A'=A then insert X (knows A evs) else knows A evs
    57          | Gets A' X    =>
    58              if A'=A then insert X (knows A evs) else knows A evs
    59          | Notes A' X    =>
    60              if A'=A then insert X (knows A evs) else knows A evs))"
    61 
    62 
    63 subsection{*Used Messages*}
    64 
    65 primrec used :: "event list => msg set"
    66 where
    67   (*Set of items that might be visible to somebody:
    68     complement of the set of fresh items.
    69     As above, message reception does extend used items *)
    70   used_Nil:  "used []         = (UN B. parts (initState B))"
    71 | used_Cons: "used (ev # evs) =
    72                  (case ev of
    73                     Says A B X => parts {X} Un (used evs)
    74                   | Gets A X   => used evs
    75                   | Notes A X  => parts {X} Un (used evs))"
    76 
    77 
    78 
    79 (* Inserted by default but later removed.  This declaration lets the file
    80 be re-loaded. Addsimps [knows_Cons, used_Nil, *)
    81 
    82 (** Simplifying   parts (insert X (knows Spy evs))
    83       = parts {X} Un parts (knows Spy evs) -- since general case loops*)
    84 
    85 lemmas parts_insert_knows_A = parts_insert [of _ "knows A evs"] for A evs
    86 
    87 lemma knows_Spy_Says [simp]:
    88      "knows Spy (Says A B X # evs) = insert X (knows Spy evs)"
    89 by auto
    90 
    91 text{*Letting the Spy see "bad" agents' notes avoids redundant case-splits
    92       on whether @{term "A=Spy"} and whether @{term "A\<in>bad"}*}
    93 lemma knows_Spy_Notes [simp]:
    94      "knows Spy (Notes A X # evs) =
    95           (if A:bad then insert X (knows Spy evs) else knows Spy evs)"
    96 apply auto
    97 done
    98 
    99 lemma knows_Spy_Gets [simp]: "knows Spy (Gets A X # evs) = knows Spy evs"
   100 by auto
   101 
   102 lemma initState_subset_knows: "initState A <= knows A evs"
   103 apply (induct_tac "evs")
   104 apply (auto split: event.split) 
   105 done
   106 
   107 lemma knows_Spy_subset_knows_Spy_Says:
   108      "knows Spy evs <= knows Spy (Says A B X # evs)"
   109 by auto
   110 
   111 lemma knows_Spy_subset_knows_Spy_Notes:
   112      "knows Spy evs <= knows Spy (Notes A X # evs)"
   113 by auto
   114 
   115 lemma knows_Spy_subset_knows_Spy_Gets:
   116      "knows Spy evs <= knows Spy (Gets A X # evs)"
   117 by auto
   118 
   119 (*Spy sees what is sent on the traffic*)
   120 lemma Says_imp_knows_Spy [rule_format]:
   121      "Says A B X \<in> set evs --> X \<in> knows Spy evs"
   122 apply (induct_tac "evs")
   123 apply (auto split: event.split) 
   124 done
   125 
   126 (*Use with addSEs to derive contradictions from old Says events containing
   127   items known to be fresh*)
   128 lemmas knows_Spy_partsEs =
   129      Says_imp_knows_Spy [THEN parts.Inj, elim_format] 
   130      parts.Body [elim_format]
   131 
   132 
   133 subsection{*The Function @{term used}*}
   134 
   135 lemma parts_knows_Spy_subset_used: "parts (knows Spy evs) <= used evs"
   136 apply (induct_tac "evs")
   137 apply (auto simp add: parts_insert_knows_A split: event.split) 
   138 done
   139 
   140 lemmas usedI = parts_knows_Spy_subset_used [THEN subsetD, intro]
   141 
   142 lemma initState_subset_used: "parts (initState B) <= used evs"
   143 apply (induct_tac "evs")
   144 apply (auto split: event.split) 
   145 done
   146 
   147 lemmas initState_into_used = initState_subset_used [THEN subsetD]
   148 
   149 lemma used_Says [simp]: "used (Says A B X # evs) = parts{X} Un used evs"
   150 by auto
   151 
   152 lemma used_Notes [simp]: "used (Notes A X # evs) = parts{X} Un used evs"
   153 by auto
   154 
   155 lemma used_Gets [simp]: "used (Gets A X # evs) = used evs"
   156 by auto
   157 
   158 
   159 lemma Notes_imp_parts_subset_used [rule_format]:
   160      "Notes A X \<in> set evs --> parts {X} <= used evs"
   161 apply (induct_tac "evs")
   162 apply (rename_tac [2] a evs')
   163 apply (induct_tac [2] "a", auto)
   164 done
   165 
   166 text{*NOTE REMOVAL--laws above are cleaner, as they don't involve "case"*}
   167 declare knows_Cons [simp del]
   168         used_Nil [simp del] used_Cons [simp del]
   169 
   170 
   171 text{*For proving theorems of the form @{term "X \<notin> analz (knows Spy evs) --> P"}
   172   New events added by induction to "evs" are discarded.  Provided 
   173   this information isn't needed, the proof will be much shorter, since
   174   it will omit complicated reasoning about @{term analz}.*}
   175 
   176 lemmas analz_mono_contra =
   177        knows_Spy_subset_knows_Spy_Says [THEN analz_mono, THEN contra_subsetD]
   178        knows_Spy_subset_knows_Spy_Notes [THEN analz_mono, THEN contra_subsetD]
   179        knows_Spy_subset_knows_Spy_Gets [THEN analz_mono, THEN contra_subsetD]
   180 
   181 lemmas analz_impI = impI [where P = "Y \<notin> analz (knows Spy evs)"] for Y evs
   182 
   183 ML
   184 {*
   185 fun analz_mono_contra_tac ctxt = 
   186   resolve_tac ctxt @{thms analz_impI} THEN' 
   187   REPEAT1 o (dresolve_tac ctxt @{thms analz_mono_contra})
   188   THEN' mp_tac ctxt
   189 *}
   190 
   191 method_setup analz_mono_contra = {*
   192     Scan.succeed (fn ctxt => SIMPLE_METHOD (REPEAT_FIRST (analz_mono_contra_tac ctxt))) *}
   193     "for proving theorems of the form X \<notin> analz (knows Spy evs) --> P"
   194 
   195 end