equal
deleted
inserted
replaced
1 (* Title: HOL/MicroJava/BV/BVLightSpec.thy |
1 (* Title: HOL/MicroJava/BV/BVLightSpec.thy |
2 ID: $Id$ |
2 ID: $Id$ |
3 Author: Gerwin Klein |
3 Author: Gerwin Klein |
4 Copyright 1999 Technische Universitaet Muenchen |
4 Copyright 1999 Technische Universitaet Muenchen |
5 |
|
6 Specification of a lightweight bytecode verifier |
|
7 *) |
5 *) |
|
6 |
|
7 header {* Specification of the LBV *} |
|
8 |
8 |
9 |
9 theory LBVSpec = BVSpec:; |
10 theory LBVSpec = BVSpec:; |
10 |
11 |
11 types |
12 types |
12 certificate = "state_type option list" |
13 certificate = "state_type option list" |
82 |
83 |
83 consts |
84 consts |
84 wtl_CH :: "[check_object,jvm_prog,state_type,state_type,p_count,p_count] \\<Rightarrow> bool"; |
85 wtl_CH :: "[check_object,jvm_prog,state_type,state_type,p_count,p_count] \\<Rightarrow> bool"; |
85 primrec |
86 primrec |
86 "wtl_CH (Checkcast C) G s s' max_pc pc = |
87 "wtl_CH (Checkcast C) G s s' max_pc pc = |
87 (let (ST,LT) = s |
88 (let (ST,LT) = s |
88 in |
89 in |
89 pc+1 < max_pc \\<and> |
90 pc+1 < max_pc \\<and> |
90 is_class G C \\<and> |
91 is_class G C \\<and> |
91 (\\<exists>rt ST'. ST = RefT rt # ST' \\<and> |
92 (\\<exists>rt ST'. ST = RefT rt # ST' \\<and> |
92 (Class C # ST' , LT) = s'))"; |
93 (Class C # ST' , LT) = s'))"; |
219 wtl_jvm_prog :: "[jvm_prog,prog_certificate] \\<Rightarrow> bool" |
220 wtl_jvm_prog :: "[jvm_prog,prog_certificate] \\<Rightarrow> bool" |
220 "wtl_jvm_prog G cert \\<equiv> |
221 "wtl_jvm_prog G cert \\<equiv> |
221 wf_prog (\\<lambda>G C (sig,rT,maxl,b). |
222 wf_prog (\\<lambda>G C (sig,rT,maxl,b). |
222 wtl_method G C (snd sig) rT maxl b (cert C sig)) G"; |
223 wtl_method G C (snd sig) rT maxl b (cert C sig)) G"; |
223 |
224 |
|
225 text {* \medskip *} |
|
226 |
224 lemma rev_eq: "\\<lbrakk>length a = n; length x = n; rev a @ b # c = rev x @ y # z\\<rbrakk> \\<Longrightarrow> a = x \\<and> b = y \\<and> c = z"; |
227 lemma rev_eq: "\\<lbrakk>length a = n; length x = n; rev a @ b # c = rev x @ y # z\\<rbrakk> \\<Longrightarrow> a = x \\<and> b = y \\<and> c = z"; |
225 proof auto; |
228 by auto; |
226 qed; |
|
227 |
229 |
228 lemma wtl_inst_unique: |
230 lemma wtl_inst_unique: |
229 "wtl_inst i G rT s0 s1 cert max_pc pc \\<longrightarrow> |
231 "wtl_inst i G rT s0 s1 cert max_pc pc \\<longrightarrow> |
230 wtl_inst i G rT s0 s1' cert max_pc pc \\<longrightarrow> s1 = s1'" (is "?P i"); |
232 wtl_inst i G rT s0 s1' cert max_pc pc \\<longrightarrow> s1 = s1'" (is "?P i"); |
231 proof (induct i); |
233 proof (induct i); |
242 case Invoke; |
244 case Invoke; |
243 have "\\<exists>x y. s0 = (x,y)"; by (simp); |
245 have "\\<exists>x y. s0 = (x,y)"; by (simp); |
244 thus "wtl_inst (MI (Invoke mname list)) G rT s0 s1 cert max_pc pc \\<longrightarrow> |
246 thus "wtl_inst (MI (Invoke mname list)) G rT s0 s1 cert max_pc pc \\<longrightarrow> |
245 wtl_inst (MI (Invoke mname list)) G rT s0 s1' cert max_pc pc \\<longrightarrow> |
247 wtl_inst (MI (Invoke mname list)) G rT s0 s1' cert max_pc pc \\<longrightarrow> |
246 s1 = s1'"; |
248 s1 = s1'"; |
247 proof (elim); |
249 proof elim; |
248 apply_end(clarsimp_tac, drule rev_eq, assumption+); |
250 apply_end(clarsimp_tac, drule rev_eq, assumption+); |
249 qed auto; |
251 qed auto; |
250 qed; |
252 qed; |
251 case MR; |
253 case MR; |
252 show "?P (MR meth_ret)"; by (induct meth_ret) auto; |
254 show "?P (MR meth_ret)"; by (induct meth_ret) auto; |
269 case Nil; |
271 case Nil; |
270 show "?P []"; by simp; |
272 show "?P []"; by simp; |
271 |
273 |
272 case Cons; |
274 case Cons; |
273 show "?P (a # list)"; |
275 show "?P (a # list)"; |
274 proof (intro); |
276 proof intro; |
275 fix s0; fix pc; |
277 fix s0; fix pc; |
276 let "?o s0 s1" = "wtl_inst_option a G rT s0 s1 cert max_pc pc"; |
278 let "?o s0 s1" = "wtl_inst_option a G rT s0 s1 cert max_pc pc"; |
277 let "?l l s1 s2 pc" = "wtl_inst_list l G rT s1 s2 cert max_pc pc"; |
279 let "?l l s1 s2 pc" = "wtl_inst_list l G rT s1 s2 cert max_pc pc"; |
278 assume a: "?l (a#list) s0 s1 pc"; |
280 assume a: "?l (a#list) s0 s1 pc"; |
279 assume b: "?l (a#list) s0 s1' pc"; |
281 assume b: "?l (a#list) s0 s1' pc"; |