1use move_abstract_stack::AbstractStack;
16use move_binary_format::{
17 errors::PartialVMError,
18 file_format::{
19 Bytecode, CodeOffset, CompiledModule, FunctionDefinitionIndex, FunctionHandle, LocalIndex,
20 StructDefinition, StructFieldInformation,
21 },
22};
23use move_bytecode_verifier::absint::{
24 AbstractDomain, FunctionContext, JoinResult, TransferFunctions, analyze_function,
25};
26use move_bytecode_verifier_meter::{Meter, Scope};
27use move_core_types::{ident_str, vm_status::StatusCode};
28use std::{collections::BTreeMap, error::Error, num::NonZeroU64};
29use sui_types::bridge::BRIDGE_MODULE_NAME;
30use sui_types::deny_list_v1::{DENY_LIST_CREATE_FUNC, DENY_LIST_MODULE};
31use sui_types::{
32 BRIDGE_ADDRESS, SUI_FRAMEWORK_ADDRESS, SUI_SYSTEM_ADDRESS,
33 accumulator_event::ACCUMULATOR_MODULE_NAME,
34 authenticator_state::AUTHENTICATOR_STATE_MODULE_NAME,
35 clock::CLOCK_MODULE_NAME,
36 error::{ExecutionError, VMMVerifierErrorSubStatusCode},
37 id::OBJECT_MODULE_NAME,
38 randomness_state::RANDOMNESS_MODULE_NAME,
39 sui_system_state::SUI_SYSTEM_MODULE_NAME,
40};
41
42use crate::{
43 FunctionIdent, TEST_SCENARIO_MODULE_NAME, check_for_verifier_timeout,
44 to_verification_timeout_error, verification_failure,
45};
46pub(crate) const JOIN_BASE_COST: u128 = 10;
47pub(crate) const JOIN_PER_LOCAL_COST: u128 = 5;
48pub(crate) const STEP_BASE_COST: u128 = 15;
49
50#[derive(Clone, Copy, Debug, Eq, PartialEq)]
51enum AbstractValue {
52 Fresh,
53 Other,
54}
55
56const OBJECT_NEW: FunctionIdent = (SUI_FRAMEWORK_ADDRESS, OBJECT_MODULE_NAME, ident_str!("new"));
57const OBJECT_NEW_UID_FROM_HASH: FunctionIdent = (
58 SUI_FRAMEWORK_ADDRESS,
59 OBJECT_MODULE_NAME,
60 ident_str!("new_uid_from_hash"),
61);
62const OBJECT_NEW_DERIVED: FunctionIdent = (
63 SUI_FRAMEWORK_ADDRESS,
64 ident_str!("derived_object"),
65 ident_str!("claim"),
66);
67const TS_NEW_OBJECT: FunctionIdent = (
68 SUI_FRAMEWORK_ADDRESS,
69 ident_str!(TEST_SCENARIO_MODULE_NAME),
70 ident_str!("new_object"),
71);
72const SUI_SYSTEM_CREATE: FunctionIdent = (
73 SUI_SYSTEM_ADDRESS,
74 SUI_SYSTEM_MODULE_NAME,
75 ident_str!("create"),
76);
77const SUI_CLOCK_CREATE: FunctionIdent = (
78 SUI_FRAMEWORK_ADDRESS,
79 CLOCK_MODULE_NAME,
80 ident_str!("create"),
81);
82const SUI_AUTHENTICATOR_STATE_CREATE: FunctionIdent = (
83 SUI_FRAMEWORK_ADDRESS,
84 AUTHENTICATOR_STATE_MODULE_NAME,
85 ident_str!("create"),
86);
87const SUI_RANDOMNESS_STATE_CREATE: FunctionIdent = (
88 SUI_FRAMEWORK_ADDRESS,
89 RANDOMNESS_MODULE_NAME,
90 ident_str!("create"),
91);
92const SUI_DENY_LIST_CREATE: FunctionIdent = (
93 SUI_FRAMEWORK_ADDRESS,
94 DENY_LIST_MODULE,
95 DENY_LIST_CREATE_FUNC,
96);
97
98const SUI_BRIDGE_CREATE: FunctionIdent = (BRIDGE_ADDRESS, BRIDGE_MODULE_NAME, ident_str!("create"));
99const SUI_ACCUMULATOR_CREATE: FunctionIdent = (
100 SUI_FRAMEWORK_ADDRESS,
101 ACCUMULATOR_MODULE_NAME,
102 ident_str!("create"),
103);
104const SUI_COIN_REGISTRY_CREATE: FunctionIdent = (
105 SUI_FRAMEWORK_ADDRESS,
106 ident_str!("coin_registry"),
107 ident_str!("create"),
108);
109const SUI_DISPLAY_REGISTRY_CREATE: FunctionIdent = (
110 SUI_FRAMEWORK_ADDRESS,
111 ident_str!("display_registry"),
112 ident_str!("create"),
113);
114const SUI_ALIAS_CREATE: FunctionIdent = (
115 SUI_FRAMEWORK_ADDRESS,
116 ident_str!("address_alias"),
117 ident_str!("create"),
118);
119const SUI_FORWARDING_ADDRESS_CREATE: FunctionIdent = (
120 SUI_FRAMEWORK_ADDRESS,
121 ident_str!("forwarding_address"),
122 ident_str!("create"),
123);
124const FRESH_ID_FUNCTIONS: &[FunctionIdent] = &[
125 OBJECT_NEW,
126 OBJECT_NEW_UID_FROM_HASH,
127 OBJECT_NEW_DERIVED,
128 TS_NEW_OBJECT,
129];
130const FUNCTIONS_TO_SKIP: &[FunctionIdent] = &[
131 SUI_SYSTEM_CREATE,
132 SUI_CLOCK_CREATE,
133 SUI_AUTHENTICATOR_STATE_CREATE,
134 SUI_RANDOMNESS_STATE_CREATE,
135 SUI_DENY_LIST_CREATE,
136 SUI_BRIDGE_CREATE,
137 SUI_ACCUMULATOR_CREATE,
138 SUI_COIN_REGISTRY_CREATE,
139 SUI_DISPLAY_REGISTRY_CREATE,
140 SUI_ALIAS_CREATE,
141 SUI_FORWARDING_ADDRESS_CREATE,
142];
143
144impl AbstractValue {
145 pub fn join(&self, value: &AbstractValue) -> AbstractValue {
146 if self == value {
147 *value
148 } else {
149 AbstractValue::Other
150 }
151 }
152}
153
154pub fn verify_module(
155 module: &CompiledModule,
156 meter: &mut (impl Meter + ?Sized),
157) -> Result<(), ExecutionError> {
158 verify_id_leak(module, meter)
159}
160
161fn verify_id_leak(
162 module: &CompiledModule,
163 meter: &mut (impl Meter + ?Sized),
164) -> Result<(), ExecutionError> {
165 for (index, func_def) in module.function_defs.iter().enumerate() {
166 let code = match func_def.code.as_ref() {
167 Some(code) => code,
168 None => continue,
169 };
170 let handle = module.function_handle_at(func_def.function);
171 let function_context =
172 FunctionContext::new(module, FunctionDefinitionIndex(index as u16), code, handle);
173 let initial_state = AbstractState::new(&function_context);
174 let mut verifier = IDLeakAnalysis::new(module, &function_context);
175 let function_to_verify = verifier.cur_function();
176 if FUNCTIONS_TO_SKIP.contains(&function_to_verify) {
177 continue;
178 }
179 analyze_function(&function_context, meter, &mut verifier, initial_state).map_err(
180 |err| {
181 if check_for_verifier_timeout(&err.major_status()) {
183 to_verification_timeout_error(err.to_string())
184 } else if let Some(message) = err.source().as_ref() {
185 let function_name =
186 module.identifier_at(module.function_handle_at(func_def.function).name);
187 let module_name = module.self_id();
188 verification_failure(format!(
189 "{} Found in {module_name}::{function_name}",
190 message
191 ))
192 } else {
193 verification_failure(err.to_string())
194 }
195 },
196 )?;
197 }
198
199 Ok(())
200}
201
202#[derive(Clone, Debug, PartialEq, Eq)]
203pub(crate) struct AbstractState {
204 locals: BTreeMap<LocalIndex, AbstractValue>,
205}
206
207impl AbstractState {
208 pub fn new(function_context: &FunctionContext) -> Self {
210 let mut state = AbstractState {
211 locals: BTreeMap::new(),
212 };
213
214 for param_idx in 0..function_context.parameters().len() {
215 state
216 .locals
217 .insert(param_idx as LocalIndex, AbstractValue::Other);
218 }
219
220 state
221 }
222}
223
224impl AbstractDomain for AbstractState {
225 fn join(
227 &mut self,
228 state: &AbstractState,
229 meter: &mut (impl Meter + ?Sized),
230 ) -> Result<JoinResult, PartialVMError> {
231 meter.add(Scope::Function, JOIN_BASE_COST)?;
232 meter.add_items(Scope::Function, JOIN_PER_LOCAL_COST, state.locals.len())?;
233 let mut changed = false;
234 for (local, value) in &state.locals {
235 let old_value = *self.locals.get(local).unwrap_or(&AbstractValue::Other);
236 let new_value = value.join(&old_value);
237 changed |= new_value != old_value;
238 self.locals.insert(*local, new_value);
239 }
240 if changed {
241 Ok(JoinResult::Changed)
242 } else {
243 Ok(JoinResult::Unchanged)
244 }
245 }
246}
247
248struct IDLeakAnalysis<'a> {
249 binary_view: &'a CompiledModule,
250 function_context: &'a FunctionContext<'a>,
251 stack: AbstractStack<AbstractValue>,
252}
253
254impl<'a> IDLeakAnalysis<'a> {
255 fn new(binary_view: &'a CompiledModule, function_context: &'a FunctionContext<'a>) -> Self {
256 Self {
257 binary_view,
258 function_context,
259 stack: AbstractStack::new(),
260 }
261 }
262
263 fn stack_popn(&mut self, n: u64) -> Result<(), PartialVMError> {
264 let Some(n) = NonZeroU64::new(n) else {
265 return Ok(());
266 };
267 self.stack.pop_any_n(n).map_err(|e| {
268 PartialVMError::new(StatusCode::VERIFIER_INVARIANT_VIOLATION)
269 .with_message(format!("Unexpected stack error on pop_n: {e}"))
270 })
271 }
272
273 fn stack_push(&mut self, val: AbstractValue) -> Result<(), PartialVMError> {
274 self.stack.push(val).map_err(|e| {
275 PartialVMError::new(StatusCode::VERIFIER_INVARIANT_VIOLATION)
276 .with_message(format!("Unexpected stack error on push: {e}"))
277 })
278 }
279
280 fn stack_pushn(&mut self, n: u64, val: AbstractValue) -> Result<(), PartialVMError> {
281 self.stack.push_n(val, n).map_err(|e| {
282 PartialVMError::new(StatusCode::VERIFIER_INVARIANT_VIOLATION)
283 .with_message(format!("Unexpected stack error on push_n: {e}"))
284 })
285 }
286
287 fn resolve_function(&self, function_handle: &FunctionHandle) -> FunctionIdent<'a> {
288 let m = self.binary_view.module_handle_at(function_handle.module);
289 let address = *self.binary_view.address_identifier_at(m.address);
290 let module = self.binary_view.identifier_at(m.name);
291 let function = self.binary_view.identifier_at(function_handle.name);
292 (address, module, function)
293 }
294
295 fn cur_function(&self) -> FunctionIdent<'a> {
296 let fdef = self
297 .binary_view
298 .function_def_at(self.function_context.index().unwrap());
299 let handle = self.binary_view.function_handle_at(fdef.function);
300 self.resolve_function(handle)
301 }
302}
303
304impl TransferFunctions for IDLeakAnalysis<'_> {
305 type State = AbstractState;
306
307 fn execute(
308 &mut self,
309 state: &mut Self::State,
310 bytecode: &Bytecode,
311 index: CodeOffset,
312 (_first_index, last_index): (u16, u16),
313 meter: &mut (impl Meter + ?Sized),
314 ) -> Result<(), PartialVMError> {
315 execute_inner(self, state, bytecode, index, meter)?;
316 if index == last_index && !self.stack.is_empty() {
320 let msg = "Invalid stack transitions. Non-zero stack size at the end of the block"
321 .to_string();
322 debug_assert!(false, "{msg}",);
323 return Err(
324 PartialVMError::new(StatusCode::VERIFIER_INVARIANT_VIOLATION).with_message(msg),
325 );
326 }
327 Ok(())
328 }
329}
330
331fn call(
332 verifier: &mut IDLeakAnalysis,
333 function_handle: &FunctionHandle,
334) -> Result<(), PartialVMError> {
335 let parameters = verifier
336 .binary_view
337 .signature_at(function_handle.parameters);
338 verifier.stack_popn(parameters.len() as u64)?;
339
340 let return_ = verifier.binary_view.signature_at(function_handle.return_);
341 let function = verifier.resolve_function(function_handle);
342 if FRESH_ID_FUNCTIONS.contains(&function) {
343 if return_.0.len() != 1 {
344 debug_assert!(false, "{:?} should have a single return value", function);
345 return Err(PartialVMError::new(StatusCode::UNKNOWN_VERIFICATION_ERROR)
346 .with_message("Should have a single return value".to_string())
347 .with_sub_status(
348 VMMVerifierErrorSubStatusCode::MULTIPLE_RETURN_VALUES_NOT_ALLOWED as u64,
349 ));
350 }
351 verifier.stack_push(AbstractValue::Fresh)?;
352 } else {
353 verifier.stack_pushn(return_.0.len() as u64, AbstractValue::Other)?;
354 }
355 Ok(())
356}
357
358fn num_fields(struct_def: &StructDefinition) -> u64 {
359 match &struct_def.field_information {
360 StructFieldInformation::Native => 0,
361 StructFieldInformation::Declared(fields) => fields.len() as u64,
362 }
363}
364
365fn pack(
366 verifier: &mut IDLeakAnalysis,
367 struct_def: &StructDefinition,
368) -> Result<(), PartialVMError> {
369 let handle = verifier
372 .binary_view
373 .datatype_handle_at(struct_def.struct_handle);
374 let num_fields = num_fields(struct_def);
375 verifier.stack_popn(num_fields - 1)?;
376 let last_value = verifier.stack.pop().unwrap();
377 if handle.abilities.has_key() && last_value != AbstractValue::Fresh {
378 let (cur_package, cur_module, cur_function) = verifier.cur_function();
379 let msg = format!(
380 "Invalid object creation in {cur_package}::{cur_module}::{cur_function}. \
381 Object created without a newly created UID. \
382 The UID must come directly from `sui::{}::{}`, or `sui::{}::{}`. \
383 For tests, it can also come from `sui::{}::{}`",
384 OBJECT_NEW.1,
385 OBJECT_NEW.2,
386 OBJECT_NEW_DERIVED.1,
387 OBJECT_NEW_DERIVED.2,
388 TS_NEW_OBJECT.1,
389 TS_NEW_OBJECT.2
390 );
391
392 return Err(PartialVMError::new(StatusCode::UNKNOWN_VERIFICATION_ERROR)
393 .with_message(msg)
394 .with_sub_status(VMMVerifierErrorSubStatusCode::INVALID_OBJECT_CREATION as u64));
395 }
396 verifier.stack_push(AbstractValue::Other)?;
397 Ok(())
398}
399
400fn unpack(
401 verifier: &mut IDLeakAnalysis,
402 struct_def: &StructDefinition,
403) -> Result<(), PartialVMError> {
404 verifier.stack.pop().unwrap();
405 verifier.stack_pushn(num_fields(struct_def), AbstractValue::Other)
406}
407
408fn execute_inner(
409 verifier: &mut IDLeakAnalysis,
410 state: &mut AbstractState,
411 bytecode: &Bytecode,
412 _: CodeOffset,
413 meter: &mut (impl Meter + ?Sized),
414) -> Result<(), PartialVMError> {
415 meter.add(Scope::Function, STEP_BASE_COST)?;
416 match bytecode {
418 Bytecode::Pop => {
419 verifier.stack.pop().unwrap();
420 }
421 Bytecode::CopyLoc(_local) => {
422 verifier.stack_push(AbstractValue::Other)?;
424 }
425 Bytecode::MoveLoc(local) => {
426 let value = state.locals.remove(local).unwrap();
427 verifier.stack_push(value)?;
428 }
429 Bytecode::StLoc(local) => {
430 let value = verifier.stack.pop().unwrap();
431 state.locals.insert(*local, value);
432 }
433
434 Bytecode::FreezeRef
436 | Bytecode::ReadRef
438 | Bytecode::CastU8
440 | Bytecode::CastU16
441 | Bytecode::CastU32
442 | Bytecode::CastU64
443 | Bytecode::CastU128
444 | Bytecode::CastU256
445 | Bytecode::Not
446 | Bytecode::VecLen(_)
447 | Bytecode::VecPopBack(_) => {
448 verifier.stack.pop().unwrap();
449 verifier.stack_push(AbstractValue::Other)?;
450 }
451
452 Bytecode::Branch(_)
454 | Bytecode::Nop => {}
455
456 Bytecode::Eq
458 | Bytecode::Neq
459 | Bytecode::Add
460 | Bytecode::Sub
461 | Bytecode::Mul
462 | Bytecode::Mod
463 | Bytecode::Div
464 | Bytecode::BitOr
465 | Bytecode::BitAnd
466 | Bytecode::Xor
467 | Bytecode::Shl
468 | Bytecode::Shr
469 | Bytecode::Or
470 | Bytecode::And
471 | Bytecode::Lt
472 | Bytecode::Gt
473 | Bytecode::Le
474 | Bytecode::Ge
475 | Bytecode::VecImmBorrow(_)
476 | Bytecode::VecMutBorrow(_) => {
477 verifier.stack.pop().unwrap();
478 verifier.stack.pop().unwrap();
479 verifier.stack_push(AbstractValue::Other)?;
480 }
481 Bytecode::WriteRef => {
482 verifier.stack.pop().unwrap();
483 verifier.stack.pop().unwrap();
484 }
485
486 Bytecode::MutBorrowLoc(_)
488 | Bytecode::ImmBorrowLoc(_) => verifier.stack_push(AbstractValue::Other)?,
489
490 | Bytecode::MutBorrowField(_)
491 | Bytecode::MutBorrowFieldGeneric(_)
492 | Bytecode::ImmBorrowField(_)
493 | Bytecode::ImmBorrowFieldGeneric(_) => {
494 verifier.stack.pop().unwrap();
495 verifier.stack_push(AbstractValue::Other)?;
496 }
497
498 Bytecode::MoveFromDeprecated(_)
501 | Bytecode::MoveFromGenericDeprecated(_)
502 | Bytecode::MoveToDeprecated(_)
503 | Bytecode::MoveToGenericDeprecated(_)
504 | Bytecode::ImmBorrowGlobalDeprecated(_)
505 | Bytecode::MutBorrowGlobalDeprecated(_)
506 | Bytecode::ImmBorrowGlobalGenericDeprecated(_)
507 | Bytecode::MutBorrowGlobalGenericDeprecated(_)
508 | Bytecode::ExistsDeprecated(_)
509 | Bytecode::ExistsGenericDeprecated(_) => {
510 panic!("Should have been checked by global_storage_access_verifier.");
511 }
512
513 Bytecode::Call(idx) => {
514 let function_handle = verifier.binary_view.function_handle_at(*idx);
515 call(verifier, function_handle)?;
516 }
517 Bytecode::CallGeneric(idx) => {
518 let func_inst = verifier.binary_view.function_instantiation_at(*idx);
519 let function_handle = verifier.binary_view.function_handle_at(func_inst.handle);
520 call(verifier, function_handle)?;
521 }
522
523 Bytecode::Ret => {
524 verifier.stack_popn(verifier.function_context.return_().len() as u64)?
525 }
526
527 Bytecode::BrTrue(_) | Bytecode::BrFalse(_) | Bytecode::Abort => {
528 verifier.stack.pop().unwrap();
529 }
530
531 Bytecode::LdTrue | Bytecode::LdFalse | Bytecode::LdU8(_) | Bytecode::LdU16(_)| Bytecode::LdU32(_) | Bytecode::LdU64(_) | Bytecode::LdU128(_)| Bytecode::LdU256(_) | Bytecode::LdConst(_) => {
533 verifier.stack_push(AbstractValue::Other)?;
534 }
535
536 Bytecode::Pack(idx) => {
537 let struct_def = verifier.binary_view.struct_def_at(*idx);
538 pack(verifier, struct_def)?;
539 }
540 Bytecode::PackGeneric(idx) => {
541 let struct_inst = verifier.binary_view.struct_instantiation_at(*idx);
542 let struct_def = verifier.binary_view.struct_def_at(struct_inst.def);
543 pack(verifier, struct_def)?;
544 }
545 Bytecode::Unpack(idx) => {
546 let struct_def = verifier.binary_view.struct_def_at(*idx);
547 unpack(verifier, struct_def)?;
548 }
549 Bytecode::UnpackGeneric(idx) => {
550 let struct_inst = verifier.binary_view.struct_instantiation_at(*idx);
551 let struct_def = verifier.binary_view.struct_def_at(struct_inst.def);
552 unpack(verifier, struct_def)?;
553 }
554
555 Bytecode::VecPack(_, num) => {
556 verifier.stack_popn(*num )?;
557 verifier.stack_push(AbstractValue::Other)?;
558 }
559
560 Bytecode::VecPushBack(_) => {
561 verifier.stack.pop().unwrap();
562 verifier.stack.pop().unwrap();
563 }
564
565 Bytecode::VecUnpack(_, num) => {
566 verifier.stack.pop().unwrap();
567 verifier.stack_pushn(*num, AbstractValue::Other)?;
568 }
569
570 Bytecode::VecSwap(_) => {
571 verifier.stack.pop().unwrap();
572 verifier.stack.pop().unwrap();
573 verifier.stack.pop().unwrap();
574 }
575 Bytecode::PackVariant(vidx) => {
576 let handle = verifier.binary_view.variant_handle_at(*vidx);
577 let variant = verifier.binary_view.variant_def_at(handle.enum_def, handle.variant);
578 let num_fields = variant.fields.len();
579 verifier.stack_popn(num_fields as u64)?;
580 verifier.stack_push(AbstractValue::Other)?;
581 }
582 Bytecode::PackVariantGeneric(vidx) => {
583 let handle = verifier.binary_view.variant_instantiation_handle_at(*vidx);
584 let enum_inst = verifier.binary_view.enum_instantiation_at(handle.enum_def);
585 let variant = verifier.binary_view.variant_def_at(enum_inst.def, handle.variant);
586 let num_fields = variant.fields.len();
587 verifier.stack_popn(num_fields as u64)?;
588 verifier.stack_push(AbstractValue::Other)?;
589 }
590 Bytecode::UnpackVariant(vidx)
591 | Bytecode::UnpackVariantImmRef(vidx)
592 | Bytecode::UnpackVariantMutRef(vidx) => {
593 let handle = verifier.binary_view.variant_handle_at(*vidx);
594 let variant = verifier.binary_view.variant_def_at(handle.enum_def, handle.variant);
595 let num_fields = variant.fields.len();
596 verifier.stack.pop().unwrap();
597 verifier.stack_pushn(num_fields as u64, AbstractValue::Other)?;
598 }
599 Bytecode::UnpackVariantGeneric(vidx)
600 | Bytecode::UnpackVariantGenericImmRef(vidx)
601 | Bytecode::UnpackVariantGenericMutRef(vidx) => {
602 let handle = verifier.binary_view.variant_instantiation_handle_at(*vidx);
603 let enum_inst = verifier.binary_view.enum_instantiation_at(handle.enum_def);
604 let variant = verifier.binary_view.variant_def_at(enum_inst.def, handle.variant);
605 let num_fields = variant.fields.len();
606 verifier.stack.pop().unwrap();
607 verifier.stack_pushn(num_fields as u64, AbstractValue::Other)?;
608 }
609 Bytecode::VariantSwitch(_) => {
610 verifier.stack.pop().unwrap();
611 }
612 };
613 Ok(())
614}