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

sui_verifier_v2/
id_leak_verifier.rs
