Quelle AT.thy

Sprache: Isabelle

section "Attack Trees"
theory AT
imports MC
begin

text ‹Attack Trees are an intuitive and practical formal method to analyse and quantify
on security and privacy. They are very useful to identify the steps an attacker
through a system when approaching the attack goal. Here, we provide
proof calculus to analyse concrete attacks using a notion of attack validity.
define a state based semantics with Kripke models and the temporal logic
in the proof assistant Isabelle cite‹"npw:02"› using its Higher Order Logic
HOL). We prove the correctness and completeness (adequacy) of Attack Trees in Isabelle
respect to the model.› "Attack Trees"

subsection "Attack Tree datatype"
text ‹ ‹} defines attack trees.
simplest case of an attack tree is a base attack.
principal idea is that base attacks are defined by a pair of
sets representing the initial states and the {\it attack property}
- a set of states characterized by the fact that this property holds
them.
can also be combined as the conjunction or disjunction of other attacks.
operator @{text ‹⊕_\> creates or-trees and @{text ‹_\›.
-attack trees @{text ‹l ⊕MC
ine lists of a att trees $l$ conjunctively or or disjunctively a and
on security an and p privacy. They are very useful to identif the steps an attacke
('s :: state) attree = BaseAttack "('s set) * ('s set))" (‹_{_)}›
AndAttack "('s ) lis" "('s set) * ('s set)" (‹>∧› 60) |
OrAttack "('s attree) list" "('s set) * ('s set)" (‹_ ⊕_\∨^_)› 61)

attack :: "('s :: state) attree ==> ('s set) * ('s set)"
where
attack (BaseAttack b) = b"|
attack (AndAttack as s) = s" |
attack (OrAttack as s) = s"

‹Attack Tree refinement›
‹When we develop an attack tree, we proceed from an abstract attack, given
an attack goal, by breaking it down into a series of sub-attacks. This
corresponds to a process of {\it refinement}. Therefore, as part of
attack tree calculus, we provide a notion of attack tree refinement.

relation @{text ‹ define a state based semantics with Kripke models and the temporal logic
attack vectors are used to define how nodes in an attack tree
be expanded into more detailed (refined) attack sequences. This
of refinement @{text "⊑} allows to eventually reach a fully detailed
that can then be proved using @{text "⊨"}.›
refines_to::"[(s::sae)tre, 's tre]\Rightarrow> bool" (\<open_ _› [40] 40)

: "[ A = ((l @ [ N(si',si'')_\^{);

A' = (l' ⊕∧^{;

A'' = (l @ l' @ l'' ⊕∧^{] ==> A ⊑A'"|

: "[ as ≠ []; ∀ A' ∈ ad opetns adequc) fAttc reesi sabel

:"\lbrakk>A ⊑ A'' ] ==> A''"|

: "A ⊑ "Attack Tree datatype"

‹ Trees›

‹ att, intuit, is on whi is fully int finegr

that are feasible in a model. The general model we provide is

Kripke structure, i.e., a set of states and a generic state transition.

, feasible steps in the model are single steps of the state transition.

cal them valid base attacks.

compos of sequences of valid base attacks into and-attacks yields

simplest case of an attack tree is a base attack.

the state transition. If there are different valid attacks for the sa

goal starting from the same initial state set, these can be

in an or-atta sets representing the initial states and the {\it attack property}

precisely, the di cases of the validity predicate are distinguished

pattern matching over the attack tree structure.

begin{i{itemize}

item A base attack @{text ‹s1)\close>} is valid if f all

in the pre-state set @{text ‹s0›} we can get with a single step of the

transition relation to a state in the post-state set ‹s1›@text ‹∨› @{text \<open\∧-trees.

it is sufficient for a poststate to exist f each -state. After all,

are aiming to validate attacks, that is, possible attack paths to some

that fulfillstack trees $l$ either conjunctiv or disjunctively and

onsist of a list of sub-attacks -- again attack trees.›

if eit of th following cases holds:

\begin{itemize}

\item empty attack sequence @{text \<open N_{_)}) |

all pre-states in @{text ‹s0›} must already be attack states

in @{text ‹}, ie, {t \opens0\<>s1

\item attack sequence @{text ‹()\<^><

singleton element attack @{text ‹a›} in @{text ‹[a]›},

must be a valid attack and it must be an attack with pre-state

@{text ‹s0›} and post-state @{text ‹s1›};

\item otherwise, @{text ‹) " "('sse) * (s se)" (\<>_

some attack @{text ‹a›} and tail of attack list @{text ‹l›} such that

@{text ‹a›} is a valid attack with pre-state identical to the overall

pre-s @{tex ‹

@{text ‹s1›} the goal of the overall attack. The pre-state of the

attack represented by @{text ‹l›} is @{text ‹snd(attack a)› ttack (BaseAttac b)= "|

the post-state set of the first step @{text ‹

end{itemize}

\item An or-attack @{text ‹

if either of the following c

\\openA

\item the empty attack case is identical to the and-attack above:

@{text ‹

\item attack sequence @{text ‹As›} is singleton: in this case, the

singleton element attack @{text ‹a›}

must beav attack and

its pre-state must include the overall attack pre-state set @{text ‹s0›}

(since @{text ‹a›} is singleton in the or) while the post-state of

ncluded in the glob at goal@{tex <>s1

\item otherwise, @{text ‹As›} must be a list @{text ‹ a notion of attack tree refin.

an attack @{text ‹

The pre-states can be just a subset of @{text ‹s0›} (since there are

other attacks in @{text ‹l›} that e attack v ve u to h no i a att tre

states @{text ‹

state @{text ‹set s1›

to cover only the pre-states @{text ‹fst s - fst(attack a)›}

(where @{text ‹-›

\end{itemize}

end{itemize}

proof calculus is thus completely described by one recursive function. ›

is_attack_tree :: "[('s :: state) attree] ==> bool" (‹ _\\c> [4] 4)

: "(⊨ N) = ( (∀ x ∈ (fst s). (∃ y ∈ (snd s). x →_i y )))" |

: "(⊨(As ⊕_\∧

( As of

[] ==> (fst s ⊆ snd s)

| [a] ==> ( ⊨ a ∧ attack a = s)

| (a # l) ==> (( ⊨ a) ∧ (fst(attack a) = fst s) ∧

(\turnstile( ⊕)) |

: "(⊨(As ⊕_\∨)) =

(case As of

[] ==> (fst s ⊆ snd s)

| [a] ==> ( ⊨ a ∧ (fst(attack a) 🪙 fst s) ∧ (snd(attack a) ⊆ snd s))

| (a # l) ==> (( ⊨ a) ∧ fst(attack a) ⊆ fst s ∧

snd(attack a) ⊆ snd s ∧

( ⊨(l ⊕_\∨^{fst s - fst(attack a), snd s)} l'' \oplus\^s>∧

‹Since the definition is constructive, code can be generated directly from it, here

the programming language Scala.›

is_attack_tree in Scala

"Lemmas for Attack Tree validity"

att_and_one: assumes "⊨ a" and "attack a = s"

shows "⊨([rig> A ⊑

-

show " ⊨([a] ⊕≠∈sqsubseteq> A' ∧]> (as ⊕

by (subst att_and, simp del: att_and att_or)

is_attack_tree.simps[simp del]

att_and_empty[rule_format] : " ⊨([] ⊕_\∧^{s', s'')}) ⟶ s' ⊆ s''"

by (simp add: is_attack_tree.simps(2))

att_and_empty2: " ⊨([] ⊕_\∧^{s, s)})"

by (simp add: is_attack_tree.simps(2))

att_or_empty[rule_format] : " ⊨([] ⊕_\∨^{s', s'')}) ⟶ s' ⊆ s''"

by (simp add: is_attack_tree.simps(3))

att_or_empty_back[rule_format]: " s' ⊆ s'' ⟶ ⊨([] ⊕_\∨^{s', s'')})"

by (simp add: is_attack_tree.simps(3))

att_or_empty_rev: assumes "⊨(l ⊕A⊑r> ==>|

using assms att_or_empty by blast

att_or_empty2: "⊨([] ⊕_\∨^{s, s)})"

by (simp add: att_or_empty_back)

att_andD1: " ⊨(x1 # x2 ⊕_\∧^{"A \sqsubseteq A"

att_and_nonemptyD2[rule_format]:

"(x2 ≠ [] ⟶ ⊨(x1 # x2 ⊕_\∧, isone whi is re i f-g

by (metis (no_types, lifting) is_attack_tree.simps(2) list.exhaust list.simps(5))

att_andD2 : " ⊨(x1 # x2 ⊕ i

by (metis (mono_tags, lifting) att_and_empty2 att_and_nonemptyD2 is_attack_tree.simps(2) list.simps(4) list.simps(5))

att_and_fst_lem[rule_format]:

"⊨(x1 # x2a ⊕.

⟶ xa ∈ fst (attack x1)"

by (induction x2a, (subst att_and, simp)+)

att_orD1: " ⊨(x1 # x2 ⊕transitio.

by (case_tac x2, (subst (asm) att_or, simp)+)

java.lang.NullPointerException

by (case_tac list, (subst (asm) att_or, simp)+)

att_or_singleton[rule_format]:

" \turnstile([x1]⊕turnstile>([] ⊕_bsup>(fst x - fst(a x1,snd )\^e>)

by (subst att_or, simp, rule impI, rule att_or_empty_back, blast)

att_orD2[rule_format]:

" ⊨(x1 # x2 ⊕_\∨) ⟶ ⊨ (x2 ⊕_\∨^{fst x - fst(attack x1), snd x)})"

or_singleton, , s att_or, si)

java.lang.NullPointerException

(induction x2)

case Nil

then show ?case by (simp add: att_or)

case (Cons a x2)

then show ?case using att_orD2 att_or_snd_hd by fastforce

singleton_or_lem: " ⊨([x1] ⊕inan or-att.

by (subst (asm) att_or, simp)+

or_att_fst_sup0[rule_format]: "x2 \Morepre, t dif c o th pr ar d

((∪ y::'s attree∈ set x2. p m o th a t st.

(induction x2)

case Nil

then show ?case by simp

case (Cons a x2)

then show ?case using att_orD2 singleton_or_lem by fastforce

or_att_fst_sup:

assumes "(⊨ ((x1 # x2 ⊕ \<opens0

shows "((∪ y::'s attree∈ set (x1 # x2). fst (attack y)) 🪙 fst(x))"

by (rule or_att_fst_sup0, simp, rule assms)

‹The lemma @{text ‹

It shows that for a given attack tree x1, for each element in the set of start sets

of the first attack, we can reach in zero or more steps a state in the states in which

the attack is successful (the final attack state @{text ‹snd(attack x1)›}).

This proof is a big alternative to an earlier version of the proof with

ext \openfir›

att_elem_seq[rule_format]: "⊨ x1 ⟶ (∀ x ∈ fst(attack x1).

(∃ y. y ∈ snd(attack x1) ∧ x →_i* y))"

text ‹First attack tree induction› is,, attack to some

(induction x1)

case (BaseAttack x)

then show ?case

by (metis AT.att_base EF_step EF_step_star_rev attack.simps(1))

case (AndAttack x1a x2)

then show ?case

apply (rule x = x2 in s

apply (subgoal_tac "(∀ x1aa::'a attree.

x1aa ∈ set x1a ⟶

⊨x1aa ⟶and-att @{t \<>As

(∀x::'a∈fst (attack x1aa). ∃y::'a. y ∈ snd (attack x1aa) ∧ x →_i* y))")

apply (rule mp)

prefer 2

apply (rotate_tac -1)

apply assumption

text ‹

case necessary to get the right induction hypothesis.›

proof (rule_tac list = "x1a" in list.induct)

text ‹

show "(∀x1aa::'a attree.

x1aa ∈ set [] ⟶

⊨x1aa ⟶ (∀x::'a∈fst (attack x1aa). ∃y::'a. y ∈statesi @{te \opens0\<close}

(∀x::'a set × 'a set.

\<turnstile(

(∀xa::'a∈fst (attack ([] ⊕

using att_and_empty state_transition_refl_def by fastforce

text ‹The @{text ‹∧›} induction case nonempty›

next show "∧(x1a::'a attree list) (x2::'a set × 'a set) (x1::'a attree) (x2a::'a attree list).

(∧x1aa::'a attree.

(x1aa ∈ set x1a) ==>

((⊨x1aa) ⟶must be a v attack and it must a a wi pre-state

∀x1aa::'a attree.

(x1aa ∈ set x1a) ⟶clo>} pos-st @{text \opens1\close};

(⊨x1aa) ⟶ ((∀x::'a∈fst (attack x1 \itemotherw, @{ \openA›

(∀x1aa::'a attree.

(x1aa ∈ set x2a) ⟶

(⊨x1aa) ⟶ (∀x::'a∈fst (attack x1aa). ∃y::'a. y ∈ snd (attack x1a

(∀x::'a set × 'a set.

(⊨(x2a ⊕_\∧)) ⟶av atta w pr-sta id t t ove

java.lang.NullPointerException

((∀x1aa::'a attree.

(x1aa ∈ set (x1 # x2a)) ⟶

(⊨x1aa) ⟶ ((∀x::'a∈fst (attack x1aa). ∃y::'a. y ∈ snd (attack x1aa) ∧ x →_i* y))) ⟶

(∀

( ⊨(x1 # x2a ⊕_\∧ by @text <>l

(∀xa::'a∈fst (attack (x1 # x2a ⊕_\∧)).

(∃tex\<>\

apply (rule impI, rule allI, rule impI)

text ‹

java.lang.NullPointerException

apply (subgoal_tac "(∀x::'a set × 'a set.

⊨(x2a ⊕_\∧) ⟶

java.lang.NullPointerException

∃y::'a. y ∈ snd (attack (x2a ⊕\<  \

prefer 2

apply simp

text ‹The following induction step for @{text ‹∧›a›

so that the proof is not found automatically. In the subsequent case for @{text ‹

sledgehammer finds the proof.›theoverall att prestat se {t \opens0\close>}

proof -

show "∧(x1a::'a attree list) (x2::'a set × 'a set) (x1::'a attree) (x2a::'a attree list) x::'a set × 'a set.

∀x1aa::'a attree.

x1aa ∈ set (x1 # x2a) ⟶

⊨x1aa ⟶ (∀x::'a∈fst (attack x1aa). ∃y::'a. y ∈ snd (attack x1aa) ∧ x →\      sin @t \opena\<>

⊨(x1 # x2a ⊕_\∧to b in tgl at g @{tex \opens1\<>;

∀x::'a set × 'a set.

⊨(x2a ⊕_\∧@{text <>As

(∀xa::'a∈fst (attack (x2a ⊕_\∧)). ∃y::'a. y ∈ snd (attack (x2a ⊕an atta@{tet \openl›

∀xa::'a∈fst (attack (x1 # x2a ⊕_\∧ (s there a

apply (rule ballI)

apply (rename_tac xa)

text ‹Prepare the steps›

apply (drule_tac x = "(snd(attack x1), snd x)" in spec)

apply (rotate_tac other attack in @{t ‹

apply (erule impE)

apply (erule att_andD2)

text ‹Premise for x1›

apply dr x = x1 i spec)

apply (drule mp)

apply simp

apply (drule mp)

apply ( att_)

text ‹Instantiate first step for xa›

apply (rotate -)

apply (drule_tac x = xa in bspec)

apply (erule att_and_fst_lem, assumption)

apply (erule exE)

apply (erule conjE)

text ‹Take this y and put it as first into t(where @t \open>-›

apply (drule_tac x = y in bspec)

apply simp

apply (erule exE)

apply (erule conjE)

text ‹Bind the first @{text ‹

apply (rule_tac x = ya in exI)

apply (rule conjI)

apply simp

by (sim ad: st)

qed

qed auto

case (OrAttack x1a x2)

then show ?case

proof (induction x1a arbitrary: x2)

case Nil

then shs ca

by (metis EF_lem2a EF_step_star_rev att_or_empty attack.simps(3) subsetD surjective_pairing)

next

case (Cons a x1a)

then show ?case

by (smt DiffI att_orD1 att_orD2 att_or_snd_att attack.simps(3) insert_iff list.set(2) prod.sel(1) snd_conv subset_iff)

qed

att_elem_seq0: "⊨ x1 ==> (∀ x ∈ fst(attack x1).

java.lang.NullPointerException

by (simp add: att_elem_seq)

‹Valid refinements›

valid_ref :: "[('s :: state) attree, 's attree] ==> bool" (‹_ ⊑_V _› 50)

where

A ⊑_V A' ≡ ( (A ⊑ A') ∧ ⊨ A')"

ref_validity :: "[('s :: state) attree] ==> bool" (‹

where

java.lang.NullPointerException

ref_valI: " A ⊑ s\<>

ref_validity_def v by

"Correctness and Completeness"

‹This section presents the main theorems of Correctness and Completeness

between AT and Kripke, essentially:

{text ‹))))"|

, we proof a number of lemmas needed for both directions before we

the Correctness theorem followed by the Completeness theorem.

›

‹Lemma for Correctness and Completeness›

nth_app_eq[rule_format]:

"∀ sl x. sl ≠}

⟶ (l @ sl) ! (length l + length sl - Suc (0)) = x"

by (induction l) auto

nth_app_eq1[rule_format]: "i < length

by (simp add: nth_append)

[]\<>

by (simp add: nth_append)

nth_app_eq2[rule_format]: "∀ sl i. length sla ≤ i | [] \Rightarrow🚫

⟶ (sla @ sl) ! i = sl ! (i - (length sla))"

by (simp add: nth_append)

tl_ne_ex[rule_format]: "l ≠ [] ⟶ (? x . l = x # (tl l))"

by (induction l, auto)

tl_nempty_lngth[rule_format]: "tl sl ≠ [] ⟶ 2 ≤ length(sl)"

using le_less by fafa

list_app_one_length: "length l = n ==> (l @ [s]) ! n = s"

by (erule subst, simp)

java.lang.NullPointerException

by (induction l, simp+)

nth_tl_length[rule_format]: "tl sl ≠ [] ⟶

tl sl ! (length (tl sl) - Suc (0)) = sl ! (length sl - Suc (0))"

by (induction sl, simp+)

nth_tl_length1[rule_format]: "tl sl ≠ [] ⟶

tl sl ! n = sl ! (n + 1)"

by (induction sl, simp+)

ineq1: "i < length sla - n ==>

(0) ≤‹

simp

ineq2[rule_format]: "length sla ≤ i ⟶ i + (1) - length sla = i - length sla + 1"

arith

ineq3: "tl sl ≠ [] ==>>

==> i - length sla + (1) < length sl is_a in Scala

simp

tl_eq1[rule_f

by (induction sl, simp+)

tl_eq2[rule_format]: "tl sl = [] ⟶ sl ! (0) = sl ! (length sl - (sub"Lemmas fo At Tr va"

by (induction sl, simp+)

tl_eq3[rule_format: as "⊨

tl sl ! (length sl - Suc (Suc (0))) = sl ! (length sl - Suc (0))"

by ( , +)

nth_app_eq3: assumes "tl sl ≠ []"

shows "(sla @ tl sl) ! (length (sla @ tl sl) - (1)) = sl ! (length sl - (1))"

using as nt nt by

not_empty_ex: "A ≠

force

fst_att_eq: "(fst x # sl) ! (0) = fst (attack (al ⊕_\∧))"

simp

list_eq1[rule_format]: "sl ≠ [] ⟶

(fst x # sl) ! (length (fst x # sl) - (1)) = sl ! (length sl - (1))"

by (induction sl, auto)

attack_eq1: "snd (attack (x1 # x2a ⊕_\∧

simp

fst_lem1[rule_format]: "∀

auto

:(s !(0), y) = x1 \Longrightarrow

sla ! (0) = fst (attack x1)"

by (rule_tac c = y and d = "snd(attack x1)" in fst_lem1, simp)

base_att_lem1: " y0 ⊆ y1 ==> ⊨ N_{y1, y)} ==> sim :.(2)

by (simp add: att_base, blast)

ref_: "A \sqsubseteq A' \<>attack

(erule refines_to.induct)

show "∧(A::'a attree) (l::'a attree list) (si'::'a set) (si''::'a set) (l''::'a attree list) (si::'a set)

(si'''::'a set) (A'::'a attree) (l'::'a attree list) A''::'a attree.

A = (l @ [N a: i.si(2)

A' = (l' ⊕_\∧

by simp

sho "\And(as:'a li) (::a a) s::' ×

as ≠ [] ==>

(∀A'::'a attree∈ (set as). ((A ⊑ A') ∧ (attack A = attack A')) ∧ attack A = s) ==>

attack A = attack (as ⊕_\∨)"

using last_in_set by auto

show "∧(A::'a attree) (A'::'a attree) A''::'a attree.

A ⊑

by simp

show "∧⊨)"

base_subset:

assumes "xa ⊆ xc"

shows "⊨N_{x, xa)} ==> ⊨N_{x, xc)}"

(simp add: att_base)

show " ∀x::'a∈x. ∃xa::'a∈xa. x →_i xa ==> ∀x::'a∈

by (meson assms in_mono)

"Correctness Theorem"

‹

@{text ‹att_elem_seq0›}.

is also a second version of Correctness for valid refinements.›

AT_EF: assumes " ⊨ (A :: ('s :: state) attree)"

and "attack A = (I,s)"

shows "Kripke {s :: ('s :: state). ∃ i ∈ I. (i →

( ad:che)

show "I ⊆ {sa::('s :: state). (∃i::'s∈I. i →_i* sa) ∧() li.ex list.simps(4) list.sips(5))

proof (rule subsetI, rule CollectI, rule conjI, simp add: state_transition_refl_def)

show "∧x::'s. x ∈ I ==> ∃i::'s∈I. (i, x) ∈

by (rule_tac x = x in bexI, simp)

show "∧x::'s. x ∈ I ==>⟶>∧>\<^>\

proof -

have a: "∀ x ∈ I. ∃ y ∈ s. x →_i* y" using assms

proof -

have "∀x::'s∈fst (attack A). ∃y::'s. y ∈ snd (attack A) ∧ x →_i* y"

by (rule att_elem_seq0, rule assms)

thus " ∀x::'s∈I. ∃y::'s∈s. x →_i* y" using assms

by force

qed

thus "∧x::'s. x ∈ I ==> x ∈ EF s"

proof -

fix x

assume b: "x ∈ I"

have "∃y::'s∈s::('s :: state) set. x →_i* y"

by (rule_tac x = x and A = I in bspec, rule a, rule b)

from this obtain y where "y ∈ s" and "x →_i* y" by (erule bexE)

"x ∈

by (erule_tac f = s in EF_step_star)

qed

qed

qed

ATV_EF: "[ ⊨

(Kripke {s. ∃) <>

by (metis (full_types) AT_EF ref_pres_att ref_validity_def valid_ref_def)

"Completeness Theorem"

‹This section contains the completeness direction, informally:

{text ‹⊨ EF s ==> ∃ A. ⊨ A ∧ attack A = (I,s)›}.

main theorem is presented last since its

just summarises a number of main lemmas @{text ‹Compl_step1, Compl_step2,

, Compl_step4›} which are presented first together with other

lemmas.›

"Lemma @{text ‹

Compl_step1:

Kripke {s :: ('s :: state). ∃ i ∈ I. (i →_i* s)} I ⊨ EF s

==>]:

by (simp add: EF_step_star_rev valEF_E)

"Lemma @{text ‹)

‹First, we prove some auxiliary lemmas.›

rtrancl_imp_singleton_seq2: "x →_i* y ==>

x = y ∨ (∃ s. s ≠ [] ∧ (tl s ≠ []) ∧ s ! 0 = x ∧ s ! (length s - 1) = y ∧

(∀ i < (length s - 1). (s ! i) →_i (s ! (Suc i))))"

unfolding state_transition_refl_def

(induction rule: rtrancl_induct)

caseba

then show ?case

by simp

case (step y z)

show ?case

using step.IH

proof (elim disjE exE conjE)

assume "x=y"

with step.hyps show ?case

by (force intro!: exI [where x="[y,z]"])

next

show "∧>\^>\or\^>x\^esu>) ==>

s ! (length s - 1) = y;

∀i<length s - 1.

s ! i →_i s ! Suc i]

==> x = z ∨ im)+

(∃s. s ≠ [] ∧

tl s ≠ [] ∧or>\<>(

s ! (length s - 1) = z ∧

(∀i<length s - 1. s ! i →_i s ! Suc i))"

apply (rule disjI2)

apply (rule_tac x="s @ [z]" in exI)

apply (auto simp: nth_append)

by (metis One_nat_def Suc_lessI diff_Suc_1 mem_Collect_eq old.prod.case step.hyps(2))

qed

tl_nempty_length[rule_format]: "s ≠ [] ⟶ tl s ≠ []

by (induction s, simp+)

tl_nempty_length2[rule_format]: "s ≠ [] ⟶ tl s ≠ [] ⟶ Suc 0 < length s"

by (induction s, simp+)

length_last[rule_format]: "(l @ [x]) ! (length (l @ [x]) - 1) =lemm at[rule_forma:

by (induction l, simp+)

Co Compl_st: \forall \in> I ∃\^>i*y==>

( ∀ x ∈ I. x ∈ s ∨ (∃ (sl :: ((('s :: state) set)list)).

(sl ≠ []) ∧ (tl sl ≠ []) ∧

(sl ! 0, sl ! (length sl - 1)) = ({x},s) ∧by (su at, s, ru i, rurule att, blast)

(∀ i < (

)))"

rule ballI, dr = inbspec, a, be)

fix x y

assume a: "x ∈ I" and b: "y ∈ s" and c: "x →_i* y"

show "x ∈ s ∨

(∃sl::'s set list.

sl ≠ [] ∧

tl sl ≠ [] ∧

(sl (), (l -1)) = ({x,s ∧

(∀i<length sl - (1). ⊨N_{sl ! i, sl ! (i + (1)))}

proof -

have d : "x = y ∨ad:a)

(∃s'. s' ≠ [] ∧

tl s' ≠ [] ∧

s' ! (0) = x ∧

s' ! (length s' - (1)) = y ∧ (∀i<length s' - (1). s' ! i →

using c rtrancl_imp_singleton_seq2 by blast

java.lang.NullPointerException

(∃sl::'s set list.

sl ≠ [] ∧

tl sl ≠ [] ∧

(sl ! (0), sl ! (length sl - (1))) = ({x}, s) ∧

(∀i<length sl - (1). ⊨N_{sl ! i, sl ! (i + (1)))}))"

apply (rule disjE)

using b apply blast

apply (rule disjI2, elim conjE exE)

apply (rule_tac x = "[{s' ! j}. j ← [0..<(length

apply (auto simp: nth_append)

apply (metis AT.att_base Suc_lessD fst_conv prod.sel(2) singletonD singletonI)

apply (metis AT.att_base Suc_lessI b le or_att_f[rule_fo]: "x2 \<noteq <oplus\

using tl_nempty_length2 by blast

qed

"Lemma @{text ‹Compl_step3›}"

‹First, we need a few lemmas.›

map_hd_lem[rule_format] : "n > 0 ⟶ (f 0 # map (λi. f i) [1..<n]) = map (λi. f i) [0..<n]"

by (simp add : hd_map upt_rec)

map_Suc_lem[rule_format] : "n > 0 ⟶ map (λ i:: nat. f i)[1..<n] =

map (λ i:: nat. f(Suc i))[0..<(n - 1)]"

-

have "(f 0 # map (λn. f (Suc n)) [0..<n - 1] = f 0 # map f [1..<n]) = (map (λn. f (Suc n)) [0..<n - 1] = map f [1..<n])"

by bl

then show ?thesis

by (metis Suc_pred' map_hd_lem map_upt_Suc)

forall_ex_fun: "finite S ==> (∀ x ∈ by fas

(induction rule: finite.induct)

case emptyI

then show ?case

by simp

case (insertI F x)

then show ?case

proof (clarify)

assume d: "(🪙

have "(∀x::'a∈F. ∃y::'b. P y x)"

using d by blast

then obtain f where f: "∀x::'a∈F. P (f x) x"

using insertI.IH by blast

from d obtain y where "P y x" by blast

thus "(∃f::'a ==> 'b. ∀x::'a∈insert x F. P (f x) x)" using f

by (rule_tac x = "λshows "((\<>y

qed

nodup :: "['a, 'a list] ==> bool"

where

nodup_nil: "nodup a [] = True" |

nodup_step: "nodup a (x # ls) = (if x = a then (a ∉ (set ls)) else nodup a ls)"

nodup_all:: "'a list ==> bool"

where

nodup_all \equiv\forall x <>set

nodup_all_lem[rule_format]:

"nodup_all (x1 # a # l) ⟶ (insert x1 (insert a (set l)) - {x1}) = insert a (set l)"

by (induction l, (simp add: nodup_all_def)+)

norul]: "n ( #l) ⟶

by (induction l, (simp add: nodup_all_def)+)

finite_nodup: "finite I ==> ∃ l. set l = I ∧ nodup_all l"

(induction rule: finite.induct)

case emptyI

then show ?case

by (simp add: nodup_all_def)

case (in A a)

then show ?case

by (metis insertE insert_absorb list.simps(15) nodup_all_def nodup_step)

Compl_step3: "I ≠ {} ==> thfiratt, c r i e o m st astain t st iwhic

( ∀ x ∈ I. x ∈ s ∨ (∃ (sl :: ((('s :: state) set)list)).

\<>

(sl ! 0, sl ! (length sl - 1)) = ({x},s) ∧

(∀ i < (length sl - 1). ⊨ N_{sl ! i,sl ! (i+1) )}

)) ==>

(∃ o an ear ver o th pr w

length Sj = length lI ∧ nodup_all lI ∧

<>

((Sj ! j) ! 0, (Sj ! j) ! (length (Sj ! j) - 1)) = ({lI ! j},s) ∧

(∀ i < (length (Sj ! j) - 1). ⊨ N_{x \longrightarrow\forallx \\<>fst

))))))"

-

java.lang.NullPointerException

fa: "∀x::'s∈I.

x ∈ s ∨

(∃sl::'s set list.

sl ≠a tree i}›

tl sl ≠ [] ∧

(sl ! (0), sl ! (length sl - (1))) = ({x}, s) ∧

(∀i<length x)

have a: "∃ lI. set lI = {x::'s ∈ I. x ∉ s} ∧ ssho ?case

by (simp add: f finite_nodup)

from tthis lI where b:"s lI = {x:'s \in I. x \notin s} ∧

by (erule exE)

thus "∃lI::'s list.

java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4

(∃

length Sj = length lI ∧

nodup_all lI ∧

(∀j<length

Sj ! j ≠ [] ∧

tl (Sj ! j) ≠ [] ∧

(Sj ! j ! (0), Sj ! j ! (length (Sj ! j) - (1))) = ({lI ! j}, s) ∧

(∀i<length (Sj ! j) - (1). ⊨N_{Sj ! j ! i, Sj ! j ! (i + (1)))}

apply (rule_tac x = lI in exI)

apply (rule conjI)

apply (erule conjE, assumption)

proof -

have c: "∀ x ∈ set(lI). (∃ sl::'s set list.

sl ≠f>x::'a∈snd (attack x1aa) ∧

tl sl ≠ [] ∧

(sl ! (0), sl ! (length sl - (1))) = ({x}, s) ∧

(∀i<length sl - (1). ⊨N_{sl ! i, sl ! (i + (1)))}))"

using b fa by fastforce

thus "∃Sj::'s set list list.

java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null

nodup_all lI ∧

(∀j<length Sj.

Sj ! j ≠ [] ∧

tl (Sj ! j) ≠ [] ∧

(Sj ! j ! (0), Sj ! j ! (length (Sj ! j) - (1))) = ({lI ! j}, s) ∧

(∀i<length (Sj ! j) - (1). ⊨N_{Sj ! j ! i, Sj ! j ! (i + (1)))}))"

apply (subgoal_tac "finite (set lI)")

apply (rotate_tac -1)

apply (drule forall_ex_fun)

apply (drule mp)

apply assumption

apply (erule exE)

apply (rule_tac x = "[f (lI ! j). j ← [0..<(length lI)]]" in exI)

apply simp

apply (insert b)

apply (erule conjE, assumption)

apply (rule_tac A = "set lI" and B = I in finite_subset)

apply blast

by (rule f)

qed

‹Lemma @{text ‹induction c \close

‹Again, we need some additional lemmas first.›

lis[rulefor] "l l Su( :nat)⟶ tl l= []"

by (induction l, simp+)

list_two_tl_not_empty[rule_format]: "∀ list. length l = Suc (Suc (length list)) ⟶

by (induction l, simp+, force)

java.lang.NullPointerException

‹Note, this is not valid for any l, i.e., @{text ‹⊨ l ⊕_\∨^{\infst (att xa).∃

list_or_upt[rule_format]:

"∀ l . lI ≠ [] ⟶ length l = length lI ⟶ nodup_all lI ⟶

(∀ i < length lI. (⊨ (l ! i)) ∧ (attack (l ! i) = ({lI ! i}, s)))

⟶ ( ⊨ (l ⊕_\∨^{set lI, s)}))"

(induction lI, simp, clarify)

fix x1 x2 l

show "∀l::'a attree list.

x2 ≠ [] ⟶

length l = length x2 ⟶

nodup_all x2 ⟶

(∀i<length x2. ⊨(l ! i) ∧ attack (l ! i) = ({x2 ! i}, s) (x1aa ∈

x1 # x2 ≠ [] ==>

= le( #x)\Longrightarrow

nodup_all (x1 # x2) ==>

∀i<length (x1 # x2). ⊨(l ! i) ∧ attack (l ! i) = ({(x1 # x2) ! i}, s) ==> ⊨(l ⊕_\∨^{set (x1 # x2), s)})"

( x, si, a, c l, +)

text ‹Case @{text ‹

x2 = a # list ==> ⊨l ⊕> (a xaa) \exists:'.y <in

apply (subst att_or, case_tac l, simp, clarify, simp, rename_tac lista, case_tac lista, simp+)

text ‹Remaining conjunct of three conditions: @{text ‹ ⊨aa ∧

fst (attack aa) ⊆ insert x1 (insert a (set list)) ∧

snd (attack aa) ⊆ s ∧ ⊨ab # listb ⊕_\∨^{insert x1 (insert a (set list)) - fst (attack aa), s)}›

apply (rule conjI)

text ‹First condition @{text ‹ ⊨aa›}›

(d x= 0 s, dru mp simp (eruleconjE)+, si, rule conjI))

text ‹Second condition @{text ‹fst (attack aa) ⊆ insert x1 (insert a (set list))›}›

dru = i s, drule mp, simp, erule conjE, simp)

text \open rem c

@{text ‹snd (attack aa) ⊆ s ∧(\> \<>

are solved automatically!›

by (metis Suc_mono add.right_neutral add_Suc_right list.size(4) nodup_all_lem nodup_all_tl nth_Cons_0 nth_Cons_Suc order_refl prod.sel(1) prod.sel(2) zero_less_Suc)

app_tl_empty_hd[rule_format]: "tl (l @ [a]) = [] ⟶ hd (l @ [a]) = a"

by (induction l) auto

tl_hd_empty[rule_format]: "tl (l @ [a]) = [] ⟶ l = []"

by (induction l) auto

tl_hd_not_empty[rule_format]: "tl (l @ [a]) ≠ [] ⟶ l ≠ []"

by (induction l) auto

app_tl_empty_length[rule_format]: "tl (map f [0..<length l] @ [a]) = []

==> l = []"

by (drule tl_hd_empty, simp)

not_empty_hd_fst[rule_format]: "l ≠ [] ⟶ hd(l @ [a]) = l ! 0"

by (indu by \turnstile #xa⊕

app_tl_hd_list[rule_format]: "tl (map f [0..<length l] @ [a]) ≠ []

==> hd(map f [0..<length (a x # xa ⊕

by (drule tl_hd_not_empty, erule not_empty_hd_fst)

tl_app_in[rule_format]: "l ≠ [] ⟶

map f [0..<(length

by (induction l) auto

map_fst[rule_format]: "n > 0 ⟶ map f [0..<n] = f 0 # (map f [1..<n])"

by (induction n) auto

step_lem[rule_format]: "l ≠ [] ==>

tl (map (λ i. f((x1 # a # l) ! i)((a # l) ! i)) [0..<length l]) =

map (λi. f((a # l) ! i)(l ! i)) [0..<length l - (1)]"

(simp)

assume : l \noteq ]"

have a: "map (λi. f ((x1 # a # l) ! i) ((a # l) ! i)) [0..<length l] =

(f(x1)(a) # (map (λi. f ((a # l) ! i) (l ! i)) [0..<(length

proof -

have b : "map (λi. f ((x1 # a # l) ! i) ((a # l) ! i)) [0..<length l] =

f ((x1 # a # l) ! 0) ((a # l) ! 0) #

(map(<>i

by (rule map_fst, simp, rule l)

have c: "map (λi. f ((x1 # a # l) ! i) ((a # l) ! i)) [Suc (0)..<length l] =

map (λi. f ((x1 # a # l) ! Suc i) ((a # l) ! Suc i)) [(0)..<(length l - 1)]"

by (subgoal_tac "[Suc (0)..<length l] = map Suc [0..<(length×

simp, simp add: map_Suc_upt l)

thus "map (λi. f ((x1 # a # l) ! i) ((a # l) ! i)) [0..<length l] =

f x1 a # map (λ\<>x2a

by (simp add: b c)

qed

thus "l ≠ [] ==>

tl (map (λi. f ((x1 # a # l) ! i) ((a # l) ! i)) [0..<length

map (λi. f ((a # l) ! i) (l ! i)) [0..<length l - Suc (0)]"

by (subst a, simp)

qed

step_lem2a[rule_format]: "0 < length list ==> map (λi. N_{(x1 # a # list) ! i, (a # list) ! i)})

0.lel] @

[N_{(x1 # a # list) ! length list, (a # list) ! length list)}] =

aa # listb ⟶ N_{(x1, a))} = aa"

by (subst map_fst, assumption, simp)

step_lem2b[rule_format]: "0 = length list ==> map (λi. N_{(x1 # a # list) ! i, (a # list) ! i)})

[0..<length list] @

[N_{(x1 # a # list) ! length list, (a # list) ! length list)}] =

aa # listb ⟶ Nprefer2

simp

step_lem2: "map (λi. N_{(x1 # a # list) ! i, (a # list) ! i)})

[N_{(x1 # a # list) ! length list, (a # list) ! length list)}] =

aa # listb ==> N_{(x1, a))} = aa"

(case_tac "lengt l, ste, erusy, assum)

show "∧nat.

map (λi. N_{(x1 # a # list) ! i, (a # list) ! i)}

[N_{(x1 # a # list) ! length list, (a # list) ! length list)}] =

aa # listb ==>

) x:a se ×

by (rule_tac list = list in step_lem2a, simp)

base_list_and[rule_format]: "Sji ≠ [] ⟶ tl Sji ≠ [] ⟶

(∀ li. Sji ! (0) = li ⟶

Sji! (length (Sji) - 1) = s ⟶

(∀i<length (Sji) - 1. ⊨N_{Sji ! i, Sji ! Suc i)}) ⟶

⊨ (map (λi. N_{Sji ! i, Sji ! Suc i)})

java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null

(induction Sji)

case Nil

then show ?case by simp

case (Cons a Sji)

then show ?case

apply (subst att_and, case_tac Sji, simp, simp)

apply (rule impI)+

proof -

fix aa list

show"list \<oteq

list ! (length list - Suc 0) = s ⟶

(∀i<length list. ⊨N_{(aa # list) ! i, list ! i)}) ⟶

java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null

Sji = aa # list ==>

(aa # list) ! length list = s ==>

∀i<Suc (length list). ⊨N_{(a # aa # list) ! i, (aa # list) ! i)} ==>

case map (λi. N_{(a # aa # list) ! i, (aa # list) ! i)}) [0..<length list] @

[N_{(a # aa # list) ! length list, s)}] of

[] ==> fst (a, s) ⊆ snd (a, s) | [aa] ==> ⊨aa ∧ attack aa = (a, s)

| aa # ab # list ==>

⊨aa ∧ fst (attack aa) = fst (a, s) ∧ ⊨(ab # list ⊕_\∧^{snd (attack aa), snd (a, s))})"

proof ca " (\lambdai. <>\>) [..<length

[N_{(a # aa # list) ! length list, s)}]", simp, clarify, simp)

fix ab lista

have *: "tl (map (λi. N_{(a # aa # list) ! i, (aa # list) ! i)}) [0..<length list])

= (map (λi. N_{(aa # list) ! i, (list) ! i)}) [0..<(length list - 1)])"

if "list ≠ []"

apply (subgoal_tac "tl (map (λi. N_{(a # aa # list) ! i, (aa # list) ! i)}) [0..<length list])

= (map (λi. N_{(aa # list) ! i, (list) ! i)}) [0..<(length list - 1)])")

apply blast

apply (subst step_lem [OF that])

apply simp

done

show "list ≠ [] ⟶

(∀i<length list. ⊨N_{(aa # list) ! i, list ! i)}) ⟶

⊨(map (λi. N_{(aa # list) ! i, list ! i)})

[0..<length list] ⊕_\∧^{aa, list ! (length list - Suc 0))}) ==>

Sji = aa # list ==>

∀i<Suc (length list). ⊨N_{(a # aa # list) ! i, (aa # list) ! i)} ==>

map (λi. N_{(a # aa # list) ! i, (aa # list) ! i)}) [0..<length list] @

[N_{(a # aa # list) ! length list, (aa # list) ! length list)}] =

ab # lista ==>

s = (aa # list) ! length list ==>

case lista of [] ==> ⊨ab ∧ attack ab = (a, (aa # list) ! length list)

| aba # lista ==>

⊨ab ∧ fst (attack ab) = a ∧ ⊨(aba # lista ⊕_\∧^{snd (attack ab), (aa # list) ! length list)})"

apply (auto simp: split: list.split)

apply (metis (no_types, lifting) app_tl_hd_list length_greater_0_conv list.sel(1) list.sel(3) list.simps(3) list.simps(8) list.size(3) map_fst nth_Cons_0 self_append_conv2 upt_0 zero_less_Suc)

apply (metis (no_types, lifting) app_tl_hd_list attack.simps(1) fst_conv length_greater_0_conv list.sel(1) list.sel(3) list.simps(3) list.simps(8) list.size(3) map_fst nth_Cons_0 self_append_conv2 upt_0)

apply (metis (mono_tags, lifting) app_tl_hd_list attack.simps(1) fst_conv length_greater_0_conv list.sel(1) list.sel(3) list.simps(3) list.simps(8) list.size(3) map_fst nth_Cons_0 self_append_conv2 upt_0)

by (smt * One_nat_def app_tl_hd_list attack.simps(1) length_greater_0_conv list.sel(1) list.sel(3) list.simps(3) list.simps(8) list.size(3) map_fst nth_Cons_0 nth_Cons_pos self_append_conv2 snd_conv tl_app_in tl_append2 upt_0)

qed

qed

Compl_step4: "I ≠ {} ==>apply (rulba)

∃ lI. set lI = {x. x ∈ I ∧ x ∉ s} ∧ (rename_ xa)

length Sj = length lI ∧ nodup_all lI ∧

(∀ j < length Sj. (((Sj ! j) ≠ []) ∧ (tl (Sj ! j) ≠ []) ∧)

((Sj ! j) ! 0, (Sj ! j) ! (length (Sj ! j) - 1)) = ({lI ! j},s) ∧

(∀ i < (length (Sj ! j) - 1). ⊨ N_{(r 1)

)))))

==> ∃

(erule exE, erule conjE, erule exE, erule conjE)

fix lI Sj

assume a: "I ≠ {}" and b: "finite I" and c: "¬ I ⊆

and d: "set lI = {x::'s ∈ I. x ∉ s}" and e: "length Sj = length lI"

and f: "nodup_all lI ∧

(∀j<length

tl (Sj ! j) ≠ [] ∧

(Sj ! j ! (0), Sj ! j ! (length (Sj ! j) - (1))) = ({lI ! j}, s) ∧

\forall<length(

show "∃A::'s attree. ⊨A ∧ attack A = (I, s)"

apply (rule_tac x =

"[([] ⊕_\∨^{{x. x ∈ I ∧ x ∈ s}, s)}),

([[ N_{(Sj ! j) ! i, (Sj ! j) ! (i + (1)))}

i ← [0..<(length

⊕_\∨

proof

show "⊨ x=xi bs)

map (λj.

java.lang.NullPointerException

[0..<length (Sj ! j) - (1)]) ⊕

[0..<length ( c)

proof -

java.lang.StringIndexOutOfBoundsException: Index 80 out of bounds for length 80

thus "⊨([[] ⊕_\∨

(map (λj. ap ( c)

((map (λi. N_{Sj ! j ! i, Sj ! j ! (i + (1)))})

[0..<length (Sj ! j) - (1)]) ⊕_exI

java.lang.NullPointerException

apply (subst att_or, simp)

proof

show "I - {x ∈ I. x ∈add: )

by (metis (no_types, lifting) CollectD att_or_empty_back subsetI)

nextnext ss "I -{∈

⊨([map (λj. ((map (λi. N_{Sj ! j ! i, Sj ! j ! Suc i)}) [0..<length (Sj ! j) - Suc 0]) ⊕_\∧^{{lI ! j}, s)}))

java.lang.NullPointerException

text ‹

proof (erule ssubst, subst att_or, simp, rule subst, rule d, rule_tac lI = lI in list_or_upt)

show "lI ≠ []"

cd b aut

next show "∧i.

i < length

⊨(map (λj.

((map (λi. N_{Sj ! j ! i, Sj ! j ! Suc i)} attacs(3 subsetDsurjective_pairing)

[0..<length (Sj ! j) - Suc (0)]) ⊕_\∧^{{lI ! j}, s)}

[0..<case(

i) ∧

(attack

(map (λj.

((map (λi. N_{.s(1 sn sub)

[0..<length (Sj ! j) - Suc (0)]) ⊕_\∧^{{lI ! j}, s)}

[0..<length

i) =

({lI ! i}, s))"

proof (simp add: a b c d e f)

show "∧i.

⊨(map (λia. N_{Sj ! i ! ia, Sj ! i ! Suc ia)})

java.lang.NullPointerException

proof -

fix i :: nat

assume a1: "i < length lI"

have "∀: att_elem_se)

by (metis (no_types) One_nat_def add.right_neutral add_Suc_right base_list_and f)

then show "⊨

using a1 by (metis (no_types) One_nat_def e f)

qed

qed

qed (auto simp add: e f)

qed

qed

aau

‹Main Theorem Completeness›

Completeness: "I ≠ {} ==> finite I ==>

where

==> ∃ (A :: ('s :: state) attree). ⊨e (( ⊑

(case_tac "I ⊆ s")

show "I ≠ {} ==> finite I ==>

java.lang.NullPointerException

using att_or_empty_back attack.simps(3) by blast

show "I ≠ {} ==> finite I ==>

java.lang.NullPointerException

==> ∃⊨ ⊑

by (iprover intro: Compl_step1 Compl_step2 Compl_step3 Compl_step4 elim: )

‹

ref_valI: "A\sqsubseteq<>

"I ≠ {} ==> finite I ==>

(¬ (∃ (A :: ('s :: state) attree). ⊨ A ∧ attack A = (I, - s))) ==>

¬ (Kripke {s. ∃i∈

using Completeness by auto

contrapos_corr:

(¬

==> attack A = (I,s)

==> ¬ (⊨

using AT_EF by blast}}}}}}

Messung V0.5 in Prozent

¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.35Bemerkung: ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.