sui_verifier_latest/
id_leak_verifier.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4//! Objects whose struct type has key ability represent Sui objects.
5//! They have unique IDs that should never be reused. This verifier makes
6//! sure that the id field of Sui objects never get leaked.
7//! Unpack is the only bytecode that could extract the id field out of
8//! a Sui object. From there, we track the flow of the value and make
9//! sure it can never get leaked outside of the function. There are four
10//! ways it can happen:
11//! 1. Returned
12//! 2. Written into a mutable reference
13//! 3. Added to a vector
14//! 4. Passed to a function cal::;
15use 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                // Handle verification timeout specially
164                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    /// create a new abstract state
191    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    /// attempts to join state to self and returns the result
208    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        // invariant: the stack should be empty at the end of the block
299        // If it is not, something is wrong with the implementation, so throw an invariant
300        // violation
301        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    // When packing, an object whose struct type has key ability must have the first field as
352    // "id". That fields must come from one of the functions that creates a new UID.
353    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    // TODO: Better diagnostics with location
399    match bytecode {
400        Bytecode::Pop => {
401            verifier.stack.pop().unwrap();
402        }
403        Bytecode::CopyLoc(_local) => {
404            // cannot copy a UID
405            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        // Reference won't be ID.
417        Bytecode::FreezeRef
418        // ID doesn't have copy ability, hence ReadRef won't produce an ID.
419        | Bytecode::ReadRef
420        // Following are unary operators that don't apply to ID.
421        | 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        // These bytecodes don't operate on any value.
435        Bytecode::Branch(_)
436        | Bytecode::Nop => {}
437
438        // These binary operators cannot produce ID as result.
439        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        // These bytecodes produce references, and hence cannot be ID.
469        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        // These bytecodes are not allowed, and will be
481        // flagged as error in a different verifier.
482        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        // These bytecodes produce constants, and hence cannot be ID.
514        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}