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