/
SGXRefinementProof.bpl
351 lines (310 loc) · 14.2 KB
/
SGXRefinementProof.bpl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
function {:inline} sgx_eid_to_tap_eid(e: wap_addr_t) : tap_enclave_id_t;
axiom (forall v1, v2: wap_addr_t :: v1 != v2 ==> sgx_eid_to_tap_eid(v1) != sgx_eid_to_tap_eid(v2));
procedure TAPSGXRefinement()
modifies cpu_owner_map,
cpu_mem,
cpu_addr_valid,
cpu_addr_map,
cpu_enclave_id,
cpu_regs,
cpu_pc,
tap_enclave_metadata_valid,
tap_enclave_metadata_addr_map,
tap_enclave_metadata_addr_valid,
tap_enclave_metadata_addr_excl,
tap_enclave_metadata_entrypoint,
tap_enclave_metadata_pc,
tap_enclave_metadata_regs,
tap_enclave_metadata_paused,
tap_enclave_metadata_cache_conflict,
cache_valid_map,
cache_tag_map,
untrusted_regs,
untrusted_addr_map,
untrusted_addr_valid,
untrusted_pc;
modifies page_table_map,
page_table_valid,
curr_lp,
xstate,
lp_state,
mem_secs,
mem_tcs,
mem_reg,
epcm,
arbitrary_write_count;
//TAP's invariants (i.e. all invariants that are not relational w.r.t. SGX)
requires (cpu_enclave_id == tap_null_enc_id) ==> ((cpu_addr_map == untrusted_addr_map) &&
(forall v : vaddr_t :: tap_addr_perm_eq(cpu_addr_valid[v], untrusted_addr_valid[v])));
requires ((cpu_enclave_id != tap_null_enc_id) ==> tap_enclave_metadata_valid[cpu_enclave_id]);
requires (cpu_enclave_id != tap_null_enc_id) ==> ((cpu_addr_map == tap_enclave_metadata_addr_map[cpu_enclave_id]) && (cpu_addr_valid == tap_enclave_metadata_addr_valid[cpu_enclave_id]));
requires (cpu_enclave_id != tap_null_enc_id) ==> (forall v : vaddr_t :: cpu_addr_map[v] == tap_enclave_metadata_addr_map[cpu_enclave_id][v]);
requires (cpu_enclave_id != tap_null_enc_id) ==> (forall v : vaddr_t :: tap_addr_perm_eq(cpu_addr_valid[v], tap_enclave_metadata_addr_valid[cpu_enclave_id][v]));
requires (forall pa : wap_addr_t, e : tap_enclave_id_t :: (e != tap_null_enc_id && !tap_enclave_metadata_valid[e]) ==> (cpu_owner_map[pa] != e));
//all mapped addresses within the evrange are private to that enclave
requires (forall v: vaddr_t, e : tap_enclave_id_t :: tap_enclave_metadata_valid[e] ==>
((tap_enclave_metadata_addr_excl[e][v] && tap_addr_perm_v(tap_enclave_metadata_addr_valid[e][v])) ==> (cpu_owner_map[tap_enclave_metadata_addr_map[e][v]] == e)));
requires (forall pa: wap_addr_t, e: tap_enclave_id_t :: cpu_owner_map[pa] == e ==> tap_enclave_metadata_valid[e]);
requires (forall v: vaddr_t, pa: wap_addr_t, eid: tap_enclave_id_t :: tap_enclave_metadata_valid[eid] ==>
tap_enclave_metadata_addr_excl[eid][v] ==> cpu_owner_map[cpu_addr_map[v]] == eid);
//SGX's invariants (i.e. all invariants that are not relational w.r.t. TAP)
requires curr_lp == 0; //only 1 CPU core is modeled in TAP
requires (forall pa: wap_addr_t :: Epcm_valid(epcm[pa]) ==> (is_epc_address(pa) && pageof_pa(pa) == pa));
requires (forall pa: wap_addr_t :: Secs_initialized(mem_secs[pa]) ==> pageof_pa(pa) == pa);
requires (forall e : wap_addr_t :: Secs_initialized(mem_secs[e]) <==> (Epcm_valid(epcm[e]) && Epcm_pt(epcm[e]) == pt_secs)); //mem_secs and epcm are in sync about which enclaves are alive
requires (forall pa: wap_addr_t :: (is_epc_address(pa) && pageof_pa(pa) == pa && Epcm_valid(epcm[pa])) ==>
(pageof_pa(Epcm_enclavesecs(epcm[pa])) == Epcm_enclavesecs(epcm[pa]) && pageof_va(Epcm_enclaveaddress(epcm[pa])) == Epcm_enclaveaddress(epcm[pa])));
//all EPC pages for an enclave are mapping some addresses within the enclave's evrange
requires (forall e1, e2: wap_addr_t ::
(is_epc_address(e1) && is_epc_address(e2) && Epcm_valid(epcm[e1]) && Epcm_valid(epcm[e2])) ==>
(Epcm_pt(epcm[e1]) == pt_secs && Epcm_pt(epcm[e2]) == pt_reg && Epcm_enclavesecs(epcm[e2]) == e1) ==>
(GE_va(Epcm_enclaveaddress(epcm[e2]), Secs_baseaddr(mem_secs[e1])) &&
LT_va(PLUS_va(Epcm_enclaveaddress(epcm[e2]), 4095bv32), PLUS_va(Secs_baseaddr(mem_secs[e1]), Secs_size(mem_secs[e1])))));
//current enclave_ids are related
requires (cpu_enclave_id == tap_null_enc_id) <==> (!Lp_state_cr_enclave_mode(lp_state[curr_lp]));
requires ((cpu_enclave_id != tap_null_enc_id) ==> (cpu_enclave_id == sgx_eid_to_tap_eid(Lp_state_cr_active_secs(lp_state[curr_lp]))));
requires (Lp_state_cr_enclave_mode(lp_state[curr_lp]) ==> (cpu_enclave_id == sgx_eid_to_tap_eid(Lp_state_cr_active_secs(lp_state[curr_lp]))));
//both TAP and SGX have the same set of enclaves
requires (forall eid: wap_addr_t :: is_epc_address(eid) ==> (Secs_initialized(mem_secs[eid]) <==> tap_enclave_metadata_valid[sgx_eid_to_tap_eid(eid)]));
requires (forall eid: wap_addr_t :: is_epc_address(eid) ==> ((Epcm_valid(epcm[eid]) && Epcm_pt(epcm[eid]) == pt_secs) <==> (tap_enclave_metadata_valid[sgx_eid_to_tap_eid(eid)])));
//both TAP and SGX have the same evrange for their enclaves
requires (forall eid: wap_addr_t, v: vaddr_t ::
(is_epc_address(eid) && Secs_initialized(mem_secs[eid])) ==>
(GE_va(v, Secs_baseaddr(mem_secs[eid])) && LT_va(v, PLUS_va(Secs_baseaddr(mem_secs[eid]), Secs_size(mem_secs[eid])))) ==>
tap_enclave_metadata_addr_excl[sgx_eid_to_tap_eid(eid)][v]);
//physical memories are related
requires (forall pa: wap_addr_t :: cpu_mem[pa] == mem_reg[pa]);
//page tables are related
requires (forall va: vaddr_t :: (tap_addr_perm_v(cpu_addr_valid[va]) == page_table_valid[va]));
requires (forall va: vaddr_t :: page_table_valid[va] <==> (tap_addr_perm_r(cpu_addr_valid[va]) && tap_addr_perm_w(cpu_addr_valid[va]) && tap_addr_perm_x(cpu_addr_valid[va])));
requires (forall va: vaddr_t :: page_table_valid[va] ==> (cpu_addr_map[va] == page_table_map[va]));
//both TAP and SGX own the same regions
requires (forall pa: wap_addr_t :: Epcm_valid(epcm[pageof_pa(pa)]) ==> cpu_owner_map[pa] == sgx_eid_to_tap_eid(Epcm_enclavesecs(epcm[pageof_pa(pa)])));
requires (forall pa: wap_addr_t, e: wap_addr_t :: (cpu_owner_map[pa] == sgx_eid_to_tap_eid(e) && sgx_eid_to_tap_eid(e) != tap_null_enc_id) ==>
(Epcm_valid(epcm[pageof_pa(pa)]) && Epcm_enclavesecs(epcm[pageof_pa(pa)]) == e));
requires (forall e1 : wap_addr_t ::
(is_epc_address(e1) && Epcm_valid(epcm[pageof_pa(e1)]) && Epcm_pt(epcm[pageof_pa(e1)]) == pt_reg) ==>
(sgx_eid_to_tap_eid(Epcm_enclavesecs(epcm[pageof_pa(e1)])) == cpu_owner_map[e1] && cpu_owner_map[e1] != tap_null_enc_id));
requires (forall e1 : wap_addr_t :: Lp_state_cr_enclave_mode(lp_state[curr_lp]) ==>
(is_epc_address(e1) && Epcm_valid(epcm[pageof_pa(e1)]) && Epcm_pt(epcm[pageof_pa(e1)]) == pt_reg) ==>
(Epcm_enclavesecs(epcm[pageof_pa(e1)]) == Lp_state_cr_active_secs(lp_state[curr_lp])) ==>
(cpu_owner_map[e1] == cpu_enclave_id && cpu_owner_map[e1] != tap_null_enc_id));
requires (forall a: wap_addr_t, e: tap_enclave_id_t :: cpu_owner_map[a] != tap_null_enc_id ==>
(is_epc_address(a) && Epcm_valid(epcm[pageof_pa(a)]) && Epcm_pt(epcm[pageof_pa(a)]) == pt_reg && sgx_eid_to_tap_eid(Epcm_enclavesecs(epcm[pageof_pa(a)])) == cpu_owner_map[a]));
{
if (*) {
call refinement_proof_step_load();
} else if (*) {
call refinement_proof_step_store();
} else if (*) {
call refinement_proof_step_ecreate();
} else if (*) {
call refinement_proof_step_eadd_reg();
} else if (*) {
call refinement_proof_step_eextend();
} else if (*) {
call refinement_proof_step_einit();
} else if (*) {
call refinement_proof_step_eenter();
} else if (*) {
call refinement_proof_step_eexit();
} else if (*) {
call refinement_proof_step_eremove();
}
}
procedure {:inline 1} refinement_proof_step_load()
modifies cache_valid_map, cache_tag_map, cpu_addr_valid;
{
var vaddr: vaddr_t;
var sgx_api_result : sgx_api_result_t;
var tap_data, sgx_data : word_t;
var tap_exn: exception_t;
var hit: bool;
havoc vaddr;
call sgx_data, sgx_api_result := sgx_load(vaddr);
if (sgx_api_result == sgx_api_success) {
call tap_data, tap_exn, hit := load_va(vaddr);
assert (tap_exn == excp_none);
assert (tap_data == sgx_data);
}
}
procedure {:inline 1} refinement_proof_step_store()
modifies cpu_mem, cache_valid_map, cache_tag_map, cpu_addr_valid, arbitrary_write_count, mem_tcs, mem_secs, mem_reg;
{
var vaddr: vaddr_t;
var data: word_t;
var sgx_api_result : sgx_api_result_t;
var tap_exn: exception_t;
var hit: bool;
havoc vaddr, data;
call sgx_api_result := sgx_store(vaddr, data);
if (sgx_api_result == sgx_api_success) {
call tap_exn, hit := store_va(vaddr, data);
assert (tap_exn == excp_none);
}
}
procedure {:inline 1} refinement_proof_step_ecreate()
modifies mem_secs, mem_reg, mem_tcs, epcm, arbitrary_write_count;
{
var la: vaddr_t;
var secs: secs_t;
var sgx_api_result : sgx_api_result_t;
havoc la, secs;
call sgx_api_result := ecreate(la, secs);
if (sgx_api_result == sgx_api_success) {
assert true;
}
}
procedure {:inline 1} refinement_proof_step_eadd_reg()
modifies mem_secs, mem_reg, mem_tcs, epcm, arbitrary_write_count;
{
var rbx_linaddr: vaddr_t;
var rbx_secs: vaddr_t;
var rcx: vaddr_t;
var r, w, x: bool;
var d: mem_t;
var sgx_api_result : sgx_api_result_t;
havoc rbx_linaddr, rbx_secs, rcx, r, w, x, d;
call sgx_api_result := eadd_reg(rbx_linaddr, rbx_secs, rcx, r, w, x, d);
if (sgx_api_result == sgx_api_success) {
assert true;
}
}
procedure {:inline 1} refinement_proof_step_eextend()
modifies mem_secs, mem_reg, mem_tcs, arbitrary_write_count;
{
var rcx: vaddr_t;
var sgx_api_result : sgx_api_result_t;
havoc rcx;
call sgx_api_result := eextend(rcx);
if (sgx_api_result == sgx_api_success) {
assert true;
}
}
procedure {:inline 1} refinement_proof_step_einit()
modifies cpu_owner_map,
cpu_mem,
tap_enclave_metadata_valid,
tap_enclave_metadata_addr_map,
tap_enclave_metadata_addr_valid,
tap_enclave_metadata_addr_excl,
tap_enclave_metadata_entrypoint,
tap_enclave_metadata_pc,
tap_enclave_metadata_regs,
tap_enclave_metadata_paused,
tap_enclave_metadata_cache_conflict;
modifies mem_reg, mem_tcs, mem_secs, arbitrary_write_count;
{
var sigstruct_signed: sigstruct_signed_t;
var rcx: vaddr_t;
var einittoken: einittoken_t;
var sgx_api_result: sgx_api_result_t;
var tap_eid : tap_enclave_id_t;
var addr_valid: addr_valid_t;
var addr_map: addr_map_t;
var excl_vaddr : excl_vaddr_t;
var excl_map: excl_map_t;
var entrypoint: vaddr_t;
var status: enclave_op_result_t;
var secs: secs_t;
havoc sigstruct_signed, rcx, einittoken;
call sgx_api_result := einit(sigstruct_signed, rcx, einittoken);
if (sgx_api_result == sgx_api_success) {
tap_eid := sgx_eid_to_tap_eid(page_table_map[rcx]); assume tap_eid != tap_null_enc_id;
secs := mem_secs[page_table_map[rcx]];
assert !old(tap_enclave_metadata_valid[tap_eid]);
//addr_valid specifies which page table entries are valid
havoc addr_valid;
assume (forall va: vaddr_t :: page_table_valid[va] <==>
(tap_addr_perm_r(addr_valid[va]) && tap_addr_perm_w(addr_valid[va]) && tap_addr_perm_x(addr_valid[va])));
//addr_map sepcifies the address translation
havoc addr_map;
assume (forall va: vaddr_t :: page_table_valid[va] ==> (addr_map[va] == page_table_map[va]));
havoc entrypoint;
assume entrypoint == Secs_baseaddr(secs);
// executable entrypoint.
assume tap_addr_perm_x(addr_valid[entrypoint]);
// exclusive entrypoint.
assume excl_vaddr[entrypoint] && excl_map[addr_map[entrypoint]];
havoc excl_vaddr;
assume (forall va : vaddr_t ::
(GE_va(va, Secs_baseaddr(secs)) &&
LT_va(va, PLUS_va(Secs_baseaddr(secs), Secs_size(secs))))
==>
excl_vaddr[va]);
//excl_map specifies which physical regions is owned by this enclave
havoc excl_map;
assume (forall pa: wap_addr_t ::
(is_epc_address(pa) &&
Epcm_valid(epcm[pageof_pa(pa)]) &&
Epcm_pt(epcm[pageof_pa(pa)]) == pt_reg &&
Epcm_enclavesecs(epcm[pageof_pa(pa)]) == page_table_map[rcx]) ==>
excl_map[pa]);
// FIXME: we have to prove these in the rest of the refinement.
assume (forall v1, v2 : vaddr_t :: !vaddr_alias(excl_vaddr, addr_map, v1, v2)) &&
(forall v : vaddr_t :: excl_vaddr[v] ==> excl_map[addr_map[v]]) &&
(forall v : vaddr_t :: excl_vaddr[v] ==> tap_addr_perm_v(addr_valid[v]));
call status := launch(tap_eid, addr_valid, addr_map, excl_vaddr, excl_map, entrypoint);
}
}
procedure {:inline 1} refinement_proof_step_eenter()
modifies cpu_enclave_id,
cpu_addr_map,
cpu_addr_valid,
cpu_pc,
cpu_regs,
untrusted_regs,
untrusted_addr_map,
untrusted_addr_valid,
untrusted_pc;
modifies mem_reg, mem_tcs, mem_secs, lp_state, arbitrary_write_count;
{
var rbx: vaddr_t;
var sgx_api_result: sgx_api_result_t;
var status: enclave_op_result_t;
var tap_eid : tap_enclave_id_t;
havoc rbx;
call sgx_api_result := eenter(rbx);
if (sgx_api_result == sgx_api_success) {
tap_eid := sgx_eid_to_tap_eid(Epcm_enclavesecs(epcm[pageof_pa(page_table_map[rbx])]));
call status := enter(tap_eid);
assert status == enclave_op_success;
}
}
procedure {:inline 1} refinement_proof_step_eexit()
modifies cpu_enclave_id,
cpu_addr_map,
cpu_addr_valid,
cpu_regs,
cpu_pc,
tap_enclave_metadata_addr_map,
tap_enclave_metadata_addr_valid,
tap_enclave_metadata_pc,
tap_enclave_metadata_paused;
modifies mem_reg, mem_tcs, mem_secs, xstate, lp_state, arbitrary_write_count;
{
var sgx_api_result: sgx_api_result_t;
var status: enclave_op_result_t;
call sgx_api_result := eexit();
if (sgx_api_result == sgx_api_success) {
call status := exit();
assert status == enclave_op_success;
}
}
procedure {:inline 1} refinement_proof_step_eremove()
modifies cpu_mem, cpu_owner_map, tap_enclave_metadata_regs, tap_enclave_metadata_valid, tap_enclave_metadata_pc;
modifies epcm;
{
var sgx_api_result: sgx_api_result_t;
var status: enclave_op_result_t;
var rcx: vaddr_t;
var epc_pa: wap_addr_t;
call sgx_api_result := eremove(rcx);
if (sgx_api_result == sgx_api_success) {
epc_pa := pageof_pa(page_table_map[rcx]);
if (Epcm_pt(epcm[epc_pa]) == pt_secs) {
call status := destroy(sgx_eid_to_tap_eid(page_table_map[pageof_va(rcx)]));
assert status == enclave_op_success;
}
}
}