CVE-2023-36184 (Rust, published 2023-09-08T02:15Z)
Description: value: CMysten Labs Sui blockchain v1.2.0 was discovered to contain a stack overflow via the component /spec/openrpc.json.
Severity: nan (CVSS v3 base score: 7.5)
Weakness: CWE-787 \u2014 Out-of-bounds Write
The product writes data past the end, or before the beginning, of the intended buffer.
Repository: https://github.com/aptos-labs/aptos-core
Files changed:
aptos-move/aptos-vm/src/move_vm_ext/vm.rs
aptos-move/framework/move-stdlib/tests/bcs_tests.move
third_party/move/move-stdlib/nursery/tests/event_tests.move
third_party/move/move-stdlib/tests/bcs_tests.move
third_party/move/move-vm/runtime/src/config.rs
third_party/move/move-vm/runtime/src/interpreter.rs
third_party/move/move-vm/runtime/src/loader.rs
third_party/move/move-vm/transactional-tests/tests/recursion/runtime_layout_deeply_nested.exp
third_party/move/move-vm/transactional-tests/tests/recursion/runtime_layout_deeply_nested.mvir
third_party/move/move-vm/types/src/loaded_data/runtime_types.rs
types/src/on_chain_config/timed_features.rs
Commit message: cherry-pick: improved value depth checks in the VM (#8488)



Vulnerable code:
    #[expected_failure(abort_code = 0, location = std::event)]
    #[expected_failure(abort_code = 453, location = std::bcs)]
        StructFieldInformation, TableIndex, Visibility,
    loaded_data::runtime_types::{CachedStructIndex, StructType, Type},
            SignatureToken::TypeParameter(idx) => Type::TyParam(*idx as usize),
                .sum::<usize>()
        map: &mut BTreeMap<usize, &'a Type>,
            if let Option::Some(t) = map.get(&i) {
                let mut sum_nodes: usize = 1;
        let mut sum_nodes: usize = 1;
        // This prevents constructing larger and lager types via struct instantiation.
        let mut sum_nodes: usize = 1;
    node_count: Option<usize>,
    annotated_node_count: Option<usize>,
const VALUE_DEPTH_MAX: usize = 128;
const MAX_TYPE_TO_LAYOUT_NODES: usize = 256;
const MAX_TYPE_INSTANTIATION_NODES: usize = 128;
    fn count_type_nodes(&self, ty: &Type) -> usize {
        count: &mut usize,
        depth: usize,
        count: &mut usize,
        depth: usize,
        count: &mut usize,
        depth: usize,
        count: &mut usize,
        depth: usize,
    offsets: [(FunctionDefinitionIndex(8), 3)],
task 3 'run'. lines 89-97:
    offsets: [(FunctionDefinitionIndex(9), 4)],

    // hits VM_MAX_VALUE_DEPTH_REACHED
    file_format::{AbilitySet, SignatureToken, StructDefinitionIndex, StructTypeParameter},
    TyParam(usize),
        F: Fn(usize, usize) -> PartialVMResult<Type> + Copy,
            |idx, depth| match ty_args.get(idx) {

Fixed code:
                    max_value_nest_depth: Some(128),
    /* Deactivated because we now limit the depth of values you could create inside the VM
    */
    #[expected_failure] // VM_MAX_VALUE_DEPTH_REACHED
    #[expected_failure] // VM_MAX_VALUE_DEPTH_REACHED
pub const DEFAULT_MAX_VALUE_NEST_DEPTH: u64 = 128;

    /// Maximum value nest depth for structs
    pub max_value_nest_depth: Option<u64>,
            max_value_nest_depth: Some(DEFAULT_MAX_VALUE_NEST_DEPTH),
fn check_depth_of_type(resolver: &Resolver, ty: &Type) -> PartialVMResult<()> {
    // Start at 1 since we always call this right before we add a new node to the value's depth.
    let max_depth = match resolver.loader().vm_config().max_value_nest_depth {
        Some(max_depth) => max_depth,
        None => return Ok(()),
    };
    check_depth_of_type_impl(resolver, ty, max_depth, 1)?;
    Ok(())
}

fn check_depth_of_type_impl(
    resolver: &Resolver,
    ty: &Type,
    max_depth: u64,
    depth: u64,
) -> PartialVMResult<u64> {
    macro_rules! check_depth {
        ($additional_depth:expr) => {{
            let new_depth = depth.saturating_add($additional_depth);
            if new_depth > max_depth {
                return Err(PartialVMError::new(StatusCode::VM_MAX_VALUE_DEPTH_REACHED));
            } else {
                new_depth
            }
        }};
    }

    // Calculate depth of the type itself
    let ty_depth = match ty {
        Type::Bool
        | Type::U8
        | Type::U16
        | Type::U32
        | Type::U64
        | Type::U128
        | Type::U256
        | Type::Address
        | Type::Signer => check_depth!(0),
        // Even though this is recursive this is OK since the depth of this recursion is
        // bounded by the depth of the type arguments, which we have already checked.
        Type::Reference(ty) | Type::MutableReference(ty) | Type::Vector(ty) => {
            check_depth_of_type_impl(resolver, ty, max_depth, check_depth!(1))?
        },
        Type::Struct(si) => {
            let struct_type = resolver.loader().get_struct_type(*si).ok_or_else(|| {
                PartialVMError::new(StatusCode::UNKNOWN_INVARIANT_VIOLATION_ERROR)
                    .with_message("Struct Definition not resolved".to_string())
            })?;
            check_depth!(struct_type
                .depth
                .as_ref()
                .ok_or_else(|| { PartialVMError::new(StatusCode::VM_MAX_VALUE_DEPTH_REACHED) })?
                .solve(&[]))
        },
        // NB: substitution must be performed before calling this function
        Type::StructInstantiation(si, ty_args) => {
            // Calculate depth of all type arguments, and make sure they themselves are not too deep.
            let ty_arg_depths = ty_args
                .iter()
                .map(|ty| {
                    // Ty args should be fully resolved and not need any type arguments
                    check_depth_of_type_impl(resolver, ty, max_depth, check_depth!(0))
                })
                .collect::<PartialVMResult<Vec<_>>>()?;
            let struct_type = resolver.loader().get_struct_type(*si).ok_or_else(|| {
                PartialVMError::new(StatusCode::UNKNOWN_INVARIANT_VIOLATION_ERROR)
                    .with_message("Struct Definition not resolved".to_string())
            })?;
            check_depth!(struct_type
                .depth
                .as_ref()
                .ok_or_else(|| { PartialVMError::new(StatusCode::VM_MAX_VALUE_DEPTH_REACHED) })?
                .solve(&ty_arg_depths))
        },
        Type::TyParam(_) => {
            return Err(
                PartialVMError::new(StatusCode::UNKNOWN_INVARIANT_VIOLATION_ERROR)
                    .with_message("Type parameter should be fully resolved".to_string()),
            )
        },
    };

    Ok(ty_depth)
}

                        let struct_type = resolver.get_struct_type(*sd_idx);
                        check_depth_of_type(resolver, &struct_type)?;
                        let ty = resolver.instantiate_generic_type(*si_idx, self.ty_args())?;
                        check_depth_of_type(resolver, &ty)?;
                        check_depth_of_type(resolver, &ty)?;
        StructFieldInformation, TableIndex, TypeParameterIndex, Visibility,
    loaded_data::runtime_types::{CachedStructIndex, DepthFormula, StructType, Type},

        let struct_defs_len = module.struct_defs.len();

        let mut depth_cache = BTreeMap::new();

        for cached_idx in starting_idx..(starting_idx + struct_defs_len) {
            self.calculate_depth_of_struct(CachedStructIndex(cached_idx), &mut depth_cache)
                .map_err(|err| err.finish(Location::Undefined))?;
        }
        debug_assert!(depth_cache.len() == struct_defs_len);
        for (cache_idx, depth) in depth_cache {
            match Arc::get_mut(self.structs.get_mut(cache_idx.0).unwrap()) {
                Some(struct_type) => struct_type.depth = Some(depth),
                None => {
                    // we have pending references to the `Arc` which is impossible,
                    // given the code that adds the `Arc` is above and no reference to
                    // it should exist.
                    // So in the spirit of not crashing we just leave it as None and
                    // log the issue.
                    error!("Arc<StructType> cannot have any live reference while publishing");
                },
            }
        }

            depth: None,
            SignatureToken::TypeParameter(idx) => Type::TyParam(*idx),

    fn calculate_depth_of_struct(
        &self,
        def_idx: CachedStructIndex,
        depth_cache: &mut BTreeMap<CachedStructIndex, DepthFormula>,
    ) -> PartialVMResult<DepthFormula> {
        let struct_type = &self.struct_at(def_idx);

        // If we've already computed this structs depth, no more work remains to be done.
        if let Some(form) = &struct_type.depth {
            return Ok(form.clone());
        }
        if let Some(form) = depth_cache.get(&def_idx) {
            return Ok(form.clone());
        }

        let formulas = struct_type
            .fields
            .iter()
            .map(|field_type| self.calculate_depth_of_type(field_type, depth_cache))
            .collect::<PartialVMResult<Vec<_>>>()?;
        let formula = DepthFormula::normalize(formulas);
        let prev = depth_cache.insert(def_idx, formula.clone());
        if prev.is_some() {
            return Err(
                PartialVMError::new(StatusCode::UNKNOWN_INVARIANT_VIOLATION_ERROR)
                    .with_message("Recursive type?".to_owned()),
            );
        }
        Ok(formula)
    }

    fn calculate_depth_of_type(
        &self,
        ty: &Type,
        depth_cache: &mut BTreeMap<CachedStructIndex, DepthFormula>,
    ) -> PartialVMResult<DepthFormula> {
        Ok(match ty {
            Type::Bool
            | Type::U8
            | Type::U64
            | Type::U128
            | Type::Address
            | Type::Signer
            | Type::U16
            | Type::U32
            | Type::U256 => DepthFormula::constant(1),
            Type::Vector(ty) | Type::Reference(ty) | Type::MutableReference(ty) => {
                let mut inner = self.calculate_depth_of_type(ty, depth_cache)?;
                inner.scale(1);
                inner
            },
            Type::TyParam(ty_idx) => DepthFormula::type_parameter(*ty_idx),
            Type::Struct(cache_idx) => {
                let mut struct_formula = self.calculate_depth_of_struct(*cache_idx, depth_cache)?;
                debug_assert!(struct_formula.terms.is_empty());
                struct_formula.scale(1);
                struct_formula
            },
            Type::StructInstantiation(cache_idx, ty_args) => {
                let ty_arg_map = ty_args
                    .iter()
                    .enumerate()
                    .map(|(idx, ty)| {
                        let var = idx as TypeParameterIndex;
                        Ok((var, self.calculate_depth_of_type(ty, depth_cache)?))
                    })
                    .collect::<PartialVMResult<BTreeMap<_, _>>>()?;
                let struct_formula = self.calculate_depth_of_struct(*cache_idx, depth_cache)?;
                let mut subst_struct_formula = struct_formula.subst(ty_arg_map)?;
                subst_struct_formula.scale(1);
                subst_struct_formula
            },
        })
    }
                .sum::<u64>()
        map: &mut BTreeMap<u16, &'a Type>,
            if let Option::Some(t) = map.get(&(i as u16)) {
                let mut sum_nodes = 1u64;
        let mut sum_nodes = 1u64;
        // This prevents constructing larger and larger types via struct instantiation.
        let mut sum_nodes = 1u64;
    node_count: Option<u64>,
    annotated_node_count: Option<u64>,
pub const VALUE_DEPTH_MAX: u64 = 128;
const MAX_TYPE_TO_LAYOUT_NODES: u64 = 256;
const MAX_TYPE_INSTANTIATION_NODES: u64 = 128;
    fn count_type_nodes(&self, ty: &Type) -> u64 {
        count: &mut u64,
        depth: u64,
        count: &mut u64,
        depth: u64,
        count: &mut u64,
        depth: u64,
        count: &mut u64,
        depth: u64,
    offsets: [(FunctionDefinitionIndex(0), 1)],
task 3 'run'. lines 89-96:
    offsets: [(FunctionDefinitionIndex(0), 1)],
    // hits VM_MAX_VALUE_DEPTH_REACHED
    file_format::{
        AbilitySet, SignatureToken, StructDefinitionIndex, StructTypeParameter, TypeParameterIndex,
    },
use std::{cmp::max, collections::BTreeMap, fmt::Debug};
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Debug)]
/// A formula describing the value depth of a type, using (the depths of) the type parameters as inputs.
///
/// It has the form of `max(CBase, T1 + C1, T2 + C2, ..)` where `Ti` is the depth of the ith type parameter
/// and `Ci` is just some constant.
///
/// This form has a special property: when you compute the max of multiple formulae, you can normalize
/// them into a single formula.
pub struct DepthFormula {
    pub terms: Vec<(TypeParameterIndex, u64)>, // Ti + Ci
    pub constant: Option<u64>,                 // Cbase
}

impl DepthFormula {
    pub fn constant(constant: u64) -> Self {
        Self {
            terms: vec![],
            constant: Some(constant),
        }
    }

    pub fn type_parameter(tparam: TypeParameterIndex) -> Self {
        Self {
            terms: vec![(tparam, 0)],
            constant: None,
        }
    }

    pub fn normalize(formulas: Vec<Self>) -> Self {
        let mut var_map = BTreeMap::new();
        let mut constant_acc = None;
        for formula in formulas {
            let Self { terms, constant } = formula;
            for (var, cur_factor) in terms {
                var_map
                    .entry(var)
                    .and_modify(|prev_factor| *prev_factor = max(cur_factor, *prev_factor))
                    .or_insert(cur_factor);
            }
            match (constant_acc, constant) {
                (_, None) => (),
                (None, Some(_)) => constant_acc = constant,
                (Some(c1), Some(c2)) => constant_acc = Some(max(c1, c2)),
            }
        }
        Self {
            terms: var_map.into_iter().collect(),
            constant: constant_acc,
        }
    }

    pub fn subst(
        &self,
        mut map: BTreeMap<TypeParameterIndex, DepthFormula>,
    ) -> PartialVMResult<DepthFormula> {
        let Self { terms, constant } = self;
        let mut formulas = vec![];
        if let Some(constant) = constant {
            formulas.push(DepthFormula::constant(*constant))
        }
        for (t_i, c_i) in terms {
            let Some(mut u_form) = map.remove(t_i) else {
                return Err(PartialVMError::new(StatusCode::UNKNOWN_INVARIANT_VIOLATION_ERROR).with_message(format!("{t_i:?} missing mapping")))
            };
            u_form.scale(*c_i);
            formulas.push(u_form)
        }
        Ok(DepthFormula::normalize(formulas))
    }

    pub fn solve(&self, tparam_depths: &[u64]) -> u64 {
        let Self { terms, constant } = self;
        let mut depth = constant.as_ref().copied().unwrap_or(0);
        for (t_i, c_i) in terms {
            depth = max(depth, tparam_depths[*t_i as usize].saturating_add(*c_i))
        }
        depth
    }

    pub fn scale(&mut self, c: u64) {
        let Self { terms, constant } = self;
        for (_t_i, c_i) in terms {
            *c_i = (*c_i).saturating_add(c);
        }
        if let Some(cbase) = constant.as_mut() {
            *cbase = (*cbase).saturating_add(c);
        }
    }
}

    pub depth: Option<DepthFormula>,
    TyParam(u16),
        F: Fn(u16, usize) -> PartialVMResult<Type> + Copy,
            |idx, depth| match ty_args.get(idx as usize) {