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

iota_verifier_latest/
id_leak_verifier.rs
