iota_verifier_latest/
id_leak_verifier.rs

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

iota_verifier_latest/
id_leak_verifier.rs
