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