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

sui_verifier_v1/
id_leak_verifier.rs
