revm_interpreter/interpreter/
analysis.rs

Help
1use revm_primitives::MAX_INITCODE_SIZE;
2
3use crate::{
4    instructions::utility::{read_i16, read_u16},
5    opcode,
6    primitives::{
7        bitvec::prelude::{bitvec, BitVec, Lsb0},
8        eof::{EofDecodeError, TypesSection},
9        legacy::JumpTable,
10        Bytecode, Bytes, Eof, LegacyAnalyzedBytecode,
11    },
12    OPCODE_INFO_JUMPTABLE, STACK_LIMIT,
13};
14use core::{convert::identity, mem};
15use std::{borrow::Cow, fmt, sync::Arc, vec, vec::Vec};
16
17/// Perform bytecode analysis.
18///
19/// The analysis finds and caches valid jump destinations for later execution as an optimization step.
20///
21/// If the bytecode is already analyzed, it is returned as-is.
22#[inline]
23pub fn to_analysed(bytecode: Bytecode) -> Bytecode {
24    let (bytes, len) = match bytecode {
25        Bytecode::LegacyRaw(bytecode) => {
26            let len = bytecode.len();
27            let mut padded_bytecode = Vec::with_capacity(len + 33);
28            padded_bytecode.extend_from_slice(&bytecode);
29            padded_bytecode.resize(len + 33, 0);
30            (Bytes::from(padded_bytecode), len)
31        }
32        n => return n,
33    };
34    let jump_table = analyze(bytes.as_ref());
35
36    Bytecode::LegacyAnalyzed(LegacyAnalyzedBytecode::new(bytes, len, jump_table))
37}
38
39/// Analyze bytecode to build a jump map.
40fn analyze(code: &[u8]) -> JumpTable {
41    let mut jumps: BitVec<u8> = bitvec![u8, Lsb0; 0; code.len()];
42
43    let range = code.as_ptr_range();
44    let start = range.start;
45    let mut iterator = start;
46    let end = range.end;
47    while iterator < end {
48        let opcode = unsafe { *iterator };
49        if opcode::JUMPDEST == opcode {
50            // SAFETY: jumps are max length of the code
51            unsafe { jumps.set_unchecked(iterator.offset_from(start) as usize, true) }
52            iterator = unsafe { iterator.offset(1) };
53        } else {
54            let push_offset = opcode.wrapping_sub(opcode::PUSH1);
55            if push_offset < 32 {
56                // SAFETY: iterator access range is checked in the while loop
57                iterator = unsafe { iterator.offset((push_offset + 2) as isize) };
58            } else {
59                // SAFETY: iterator access range is checked in the while loop
60                iterator = unsafe { iterator.offset(1) };
61            }
62        }
63    }
64
65    JumpTable(Arc::new(jumps))
66}
67
68/// Decodes `raw` into an [`Eof`] container and validates it.
69pub fn validate_raw_eof(raw: Bytes) -> Result<Eof, EofError> {
70    validate_raw_eof_inner(raw, Some(CodeType::ReturnContract))
71}
72
73/// Decodes `raw` into an [`Eof`] container and validates it.
74#[inline]
75pub fn validate_raw_eof_inner(
76    raw: Bytes,
77    first_code_type: Option<CodeType>,
78) -> Result<Eof, EofError> {
79    if raw.len() > MAX_INITCODE_SIZE {
80        return Err(EofError::Decode(EofDecodeError::InvalidEOFSize));
81    }
82    let eof = Eof::decode(raw)?;
83    validate_eof_inner(&eof, first_code_type)?;
84    Ok(eof)
85}
86
87/// Fully validates an [`Eof`] container.
88///
89/// Only place where validation happen is in Creating Transaction.
90/// Because of that we are assuming CodeType is ReturnContract.
91///
92/// Note: If needed we can make a flag that would assume ReturnContract CodeType.
93pub fn validate_eof(eof: &Eof) -> Result<(), EofError> {
94    validate_eof_inner(eof, Some(CodeType::ReturnContract))
95}
96
97#[inline]
98pub fn validate_eof_inner(eof: &Eof, first_code_type: Option<CodeType>) -> Result<(), EofError> {
99    // data needs to be filled first first container.
100    if !eof.body.is_data_filled {
101        return Err(EofError::Validation(EofValidationError::DataNotFilled));
102    }
103    if eof.body.container_section.is_empty() {
104        validate_eof_codes(eof, first_code_type)?;
105        return Ok(());
106    }
107
108    let mut stack = Vec::with_capacity(4);
109    stack.push((Cow::Borrowed(eof), first_code_type));
110
111    while let Some((eof, code_type)) = stack.pop() {
112        // Validate the current container.
113        let tracker_containers = validate_eof_codes(&eof, code_type)?;
114        // Decode subcontainers and push them to the stack.
115        for (container, code_type) in eof
116            .body
117            .container_section
118            .iter()
119            .zip(tracker_containers.into_iter())
120        {
121            stack.push((Cow::Owned(Eof::decode(container.clone())?), Some(code_type)));
122        }
123    }
124
125    Ok(())
126}
127
128/// Validates an [`Eof`] structure, without recursing into containers.
129///
130/// Returns a list of all sub containers that are accessed.
131#[inline]
132pub fn validate_eof_codes(
133    eof: &Eof,
134    this_code_type: Option<CodeType>,
135) -> Result<Vec<CodeType>, EofValidationError> {
136    if eof.body.code_section.len() != eof.body.types_section.len() {
137        return Err(EofValidationError::InvalidTypesSection);
138    }
139
140    if eof.body.code_section.is_empty() {
141        // no code sections. This should be already checked in decode.
142        return Err(EofValidationError::NoCodeSections);
143    }
144
145    // the first code section must have a type signature
146    // (0, 0x80, max_stack_height) (0 inputs non-returning function)
147    let first_types = &eof.body.types_section[0];
148    if first_types.inputs != 0 || !first_types.is_non_returning() {
149        return Err(EofValidationError::InvalidTypesSection);
150    }
151
152    // tracking access of code and sub containers.
153    let mut tracker: AccessTracker = AccessTracker::new(
154        this_code_type,
155        eof.body.code_section.len(),
156        eof.body.container_section.len(),
157    );
158
159    while let Some(index) = tracker.processing_stack.pop() {
160        // assume index is correct.
161        let code = &eof.body.code_section[index];
162        validate_eof_code(
163            code,
164            eof.header.data_size as usize,
165            index,
166            eof.body.container_section.len(),
167            &eof.body.types_section,
168            &mut tracker,
169        )?;
170    }
171
172    // iterate over accessed codes and check if all are accessed.
173    if !tracker.codes.into_iter().all(identity) {
174        return Err(EofValidationError::CodeSectionNotAccessed);
175    }
176    // iterate over all accessed subcontainers and check if all are accessed.
177    if !tracker.subcontainers.iter().all(|i| i.is_some()) {
178        return Err(EofValidationError::SubContainerNotAccessed);
179    }
180
181    if tracker.this_container_code_type == Some(CodeType::ReturnContract)
182        && !eof.body.is_data_filled
183    {
184        return Err(EofValidationError::DataNotFilled);
185    }
186
187    Ok(tracker
188        .subcontainers
189        .into_iter()
190        .map(|i| i.unwrap())
191        .collect())
192}
193
194/// EOF Error.
195#[derive(Debug, Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
196pub enum EofError {
197    Decode(EofDecodeError),
198    Validation(EofValidationError),
199}
200
201impl From<EofDecodeError> for EofError {
202    fn from(err: EofDecodeError) -> Self {
203        EofError::Decode(err)
204    }
205}
206
207impl From<EofValidationError> for EofError {
208    fn from(err: EofValidationError) -> Self {
209        EofError::Validation(err)
210    }
211}
212
213impl fmt::Display for EofError {
214    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
215        match self {
216            EofError::Decode(e) => write!(f, "Bytecode decode error: {}", e),
217            EofError::Validation(e) => write!(f, "Bytecode validation error: {}", e),
218        }
219    }
220}
221
222#[cfg(feature = "std")]
223impl std::error::Error for EofError {}
224
225#[derive(Debug, Hash, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
226pub enum EofValidationError {
227    FalsePositive,
228    /// Opcode is not known. It is not defined in the opcode table.
229    UnknownOpcode,
230    /// Opcode is disabled in EOF. For example JUMP, JUMPI, etc.
231    OpcodeDisabled,
232    /// Every instruction inside bytecode should be forward accessed.
233    /// Forward access can be a jump or sequential opcode.
234    /// In case after terminal opcode there should be a forward jump.
235    InstructionNotForwardAccessed,
236    /// Bytecode is too small and is missing immediate bytes for instruction.
237    MissingImmediateBytes,
238    /// Similar to [`EofValidationError::MissingImmediateBytes`] but for special case of RJUMPV immediate bytes.
239    MissingRJUMPVImmediateBytes,
240    /// Invalid jump into immediate bytes.
241    JumpToImmediateBytes,
242    /// Invalid jump into immediate bytes.
243    BackwardJumpToImmediateBytes,
244    /// MaxIndex in RJUMPV can't be zero. Zero max index makes it RJUMPI.
245    RJUMPVZeroMaxIndex,
246    /// Jump with zero offset would make a jump to next opcode, it does not make sense.
247    JumpZeroOffset,
248    /// EOFCREATE points to container out of bounds.
249    EOFCREATEInvalidIndex,
250    /// CALLF section out of bounds.
251    CodeSectionOutOfBounds,
252    /// CALLF to non returning function is not allowed.
253    CALLFNonReturningFunction,
254    /// CALLF stack overflow.
255    StackOverflow,
256    /// JUMPF needs to have enough outputs.
257    JUMPFEnoughOutputs,
258    /// JUMPF Stack
259    JUMPFStackHigherThanOutputs,
260    /// DATA load out of bounds.
261    DataLoadOutOfBounds,
262    /// RETF biggest stack num more then outputs.
263    RETFBiggestStackNumMoreThenOutputs,
264    /// Stack requirement is more than smallest stack items.
265    StackUnderflow,
266    /// Smallest stack items is more than types output.
267    TypesStackUnderflow,
268    /// Jump out of bounds.
269    JumpUnderflow,
270    /// Jump to out of bounds.
271    JumpOverflow,
272    /// Backward jump should have same smallest and biggest stack items.
273    BackwardJumpBiggestNumMismatch,
274    /// Backward jump should have same smallest and biggest stack items.
275    BackwardJumpSmallestNumMismatch,
276    /// Last instruction should be terminating.
277    LastInstructionNotTerminating,
278    /// Code section not accessed.
279    CodeSectionNotAccessed,
280    /// Types section invalid
281    InvalidTypesSection,
282    /// First types section is invalid.
283    /// It should have inputs 0 and outputs 0x80.
284    InvalidFirstTypesSection,
285    /// Max stack element mismatch.
286    MaxStackMismatch,
287    /// No code sections present
288    NoCodeSections,
289    /// Sub container called in two different modes.
290    /// Check [`CodeType`] for more information.
291    SubContainerCalledInTwoModes,
292    /// Sub container not accessed.
293    SubContainerNotAccessed,
294    /// Data size needs to be filled for ReturnContract type.
295    DataNotFilled,
296    /// Section is marked as non-returning but has either RETF or
297    /// JUMPF to returning section opcodes.
298    NonReturningSectionIsReturning,
299}
300
301#[derive(Clone, Debug, PartialEq, Eq)]
302pub struct AccessTracker {
303    /// This code type
304    pub this_container_code_type: Option<CodeType>,
305    /// Vector of accessed codes.
306    pub codes: Vec<bool>,
307    /// Stack of codes section that needs to be processed.
308    pub processing_stack: Vec<usize>,
309    /// Code accessed by subcontainer and expected subcontainer first code type.
310    /// EOF code can be invoked in EOFCREATE mode or used in RETURNCONTRACT opcode.
311    /// if SubContainer is called from EOFCREATE it needs to be ReturnContract type.
312    /// If SubContainer is called from RETURNCONTRACT it needs to be ReturnOrStop type.
313    ///
314    /// None means it is not accessed.
315    pub subcontainers: Vec<Option<CodeType>>,
316}
317
318impl AccessTracker {
319    /// Returns a new instance of `CodeSubContainerAccess`.
320    ///
321    /// Mark first code section as accessed and push first it to the stack.
322    ///
323    /// # Panics
324    ///
325    /// Panics if `codes_size` is zero.
326    pub fn new(
327        this_container_code_type: Option<CodeType>,
328        codes_size: usize,
329        subcontainers_size: usize,
330    ) -> Self {
331        if codes_size == 0 {
332            panic!("There should be at least one code section");
333        }
334        let mut this = Self {
335            this_container_code_type,
336            codes: vec![false; codes_size],
337            processing_stack: Vec::with_capacity(4),
338            subcontainers: vec![None; subcontainers_size],
339        };
340        this.codes[0] = true;
341        this.processing_stack.push(0);
342        this
343    }
344
345    /// Mark code as accessed.
346    ///
347    /// If code was not accessed before, it will be added to the processing stack.
348    ///
349    /// Assumes that index is valid.
350    pub fn access_code(&mut self, index: usize) {
351        let was_accessed = mem::replace(&mut self.codes[index], true);
352        if !was_accessed {
353            self.processing_stack.push(index);
354        }
355    }
356
357    pub fn set_subcontainer_type(
358        &mut self,
359        index: usize,
360        new_code_type: CodeType,
361    ) -> Result<(), EofValidationError> {
362        let Some(container) = self.subcontainers.get_mut(index) else {
363            panic!("It should not be possible")
364        };
365
366        let Some(code_type) = container else {
367            *container = Some(new_code_type);
368            return Ok(());
369        };
370
371        if *code_type != new_code_type {
372            return Err(EofValidationError::SubContainerCalledInTwoModes);
373        }
374        Ok(())
375    }
376}
377
378/// Types of code sections. It is a error if container to contain
379/// both RETURNCONTRACT and either of RETURN or STOP.
380#[derive(Clone, Copy, Debug, PartialEq, Eq)]
381pub enum CodeType {
382    /// Return contract code.
383    ReturnContract,
384    /// Return or Stop opcodes.
385    ReturnOrStop,
386}
387
388impl CodeType {
389    /// Returns true of the code is initcode.
390    pub fn is_initcode(&self) -> bool {
391        matches!(self, CodeType::ReturnContract)
392    }
393}
394
395impl fmt::Display for EofValidationError {
396    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
397        let s = match self {
398            Self::FalsePositive => "False positive",
399            Self::UnknownOpcode => "Opcode is not known",
400            Self::OpcodeDisabled => "Opcode is disabled",
401            Self::InstructionNotForwardAccessed => "Should have forward jump",
402            Self::MissingImmediateBytes => "Bytecode is missing bytes",
403            Self::MissingRJUMPVImmediateBytes => "Bytecode is missing bytes after RJUMPV opcode",
404            Self::JumpToImmediateBytes => "Invalid jump",
405            Self::BackwardJumpToImmediateBytes => "Invalid backward jump",
406            Self::RJUMPVZeroMaxIndex => "Used RJUMPV with zero as MaxIndex",
407            Self::JumpZeroOffset => "Used JUMP with zero as offset",
408            Self::EOFCREATEInvalidIndex => "EOFCREATE points to out of bound index",
409            Self::CodeSectionOutOfBounds => "CALLF index is out of bounds",
410            Self::CALLFNonReturningFunction => "CALLF was used on non-returning function",
411            Self::StackOverflow => "CALLF stack overflow",
412            Self::JUMPFEnoughOutputs => "JUMPF needs more outputs",
413            Self::JUMPFStackHigherThanOutputs => "JUMPF stack is too high for outputs",
414            Self::DataLoadOutOfBounds => "DATALOAD is out of bounds",
415            Self::RETFBiggestStackNumMoreThenOutputs => {
416                "RETF biggest stack num is more than outputs"
417            }
418            Self::StackUnderflow => "Stack requirement is above smallest stack items",
419            Self::TypesStackUnderflow => "Smallest stack items is more than output type",
420            Self::JumpUnderflow => "Jump destination is too low",
421            Self::JumpOverflow => "Jump destination is too high",
422            Self::BackwardJumpBiggestNumMismatch => {
423                "Backward jump has different biggest stack item"
424            }
425            Self::BackwardJumpSmallestNumMismatch => {
426                "Backward jump has different smallest stack item"
427            }
428            Self::LastInstructionNotTerminating => {
429                "Last instruction of bytecode is not terminating"
430            }
431            Self::CodeSectionNotAccessed => "Code section was not accessed",
432            Self::InvalidTypesSection => "Invalid types section",
433            Self::InvalidFirstTypesSection => "Invalid first types section",
434            Self::MaxStackMismatch => "Max stack element mismatchs",
435            Self::NoCodeSections => "No code sections",
436            Self::SubContainerCalledInTwoModes => "Sub container called in two modes",
437            Self::SubContainerNotAccessed => "Sub container not accessed",
438            Self::DataNotFilled => "Data not filled",
439            Self::NonReturningSectionIsReturning => "Non returning section is returning",
440        };
441        f.write_str(s)
442    }
443}
444
445#[cfg(feature = "std")]
446impl std::error::Error for EofValidationError {}
447
448/// Validates that:
449/// * All instructions are valid.
450/// * It ends with a terminating instruction or RJUMP.
451/// * All instructions are accessed by forward jumps or .
452///
453/// Validate stack requirements and if all codes sections are used.
454pub fn validate_eof_code(
455    code: &[u8],
456    data_size: usize,
457    this_types_index: usize,
458    num_of_containers: usize,
459    types: &[TypesSection],
460    tracker: &mut AccessTracker,
461) -> Result<(), EofValidationError> {
462    let this_types = &types[this_types_index];
463
464    #[derive(Debug, Copy, Clone)]
465    struct InstructionInfo {
466        /// Is immediate byte, jumps can't happen on this part of code.
467        is_immediate: bool,
468        /// Have forward jump to this opcode. Used to check if opcode
469        /// after termination is accessed.
470        is_jumpdest: bool,
471        /// Smallest number of stack items accessed by jumps or sequential opcodes.
472        smallest: i32,
473        /// Biggest number of stack items accessed by jumps or sequential opcodes.
474        biggest: i32,
475    }
476
477    impl InstructionInfo {
478        #[inline]
479        fn mark_as_immediate(&mut self) -> Result<(), EofValidationError> {
480            if self.is_jumpdest {
481                // Jump to immediate bytes.
482                return Err(EofValidationError::JumpToImmediateBytes);
483            }
484            self.is_immediate = true;
485            Ok(())
486        }
487    }
488
489    impl Default for InstructionInfo {
490        fn default() -> Self {
491            Self {
492                is_immediate: false,
493                is_jumpdest: false,
494                smallest: i32::MAX,
495                biggest: i32::MIN,
496            }
497        }
498    }
499
500    // all bytes that are intermediate.
501    let mut jumps = vec![InstructionInfo::default(); code.len()];
502    let mut is_after_termination = false;
503
504    let mut next_smallest = this_types.inputs as i32;
505    let mut next_biggest = this_types.inputs as i32;
506
507    let mut is_returning = false;
508
509    let mut i = 0;
510    // We can check validity and jump destinations in one pass.
511    while i < code.len() {
512        let op = code[i];
513        let opcode = &OPCODE_INFO_JUMPTABLE[op as usize];
514
515        let Some(opcode) = opcode else {
516            // err unknown opcode.
517            return Err(EofValidationError::UnknownOpcode);
518        };
519
520        if opcode.is_disabled_in_eof() {
521            // Opcode is disabled in EOF
522            return Err(EofValidationError::OpcodeDisabled);
523        }
524
525        let this_instruction = &mut jumps[i];
526
527        // update biggest/smallest values for next instruction only if it is not after termination.
528        if !is_after_termination {
529            this_instruction.smallest = core::cmp::min(this_instruction.smallest, next_smallest);
530            this_instruction.biggest = core::cmp::max(this_instruction.biggest, next_biggest);
531        }
532
533        let this_instruction = *this_instruction;
534
535        // Opcodes after termination should be accessed by forward jumps.
536        if is_after_termination && !this_instruction.is_jumpdest {
537            // opcode after termination was not accessed.
538            return Err(EofValidationError::InstructionNotForwardAccessed);
539        }
540        is_after_termination = opcode.is_terminating();
541
542        // mark immediate as non-jumpable. RJUMPV is special case covered later.
543        if opcode.immediate_size() != 0 {
544            // check if the opcode immediate are within the bounds of the code
545            if i + opcode.immediate_size() as usize >= code.len() {
546                // Malfunctional code
547                return Err(EofValidationError::MissingImmediateBytes);
548            }
549
550            // mark immediate bytes as non-jumpable.
551            for imm in 1..opcode.immediate_size() as usize + 1 {
552                // SAFETY: immediate size is checked above.
553                jumps[i + imm].mark_as_immediate()?;
554            }
555        }
556        // IO diff used to generate next instruction smallest/biggest value.
557        let mut stack_io_diff = opcode.io_diff() as i32;
558        // how many stack items are required for this opcode.
559        let mut stack_requirement = opcode.inputs() as i32;
560        // additional immediate bytes for RJUMPV, it has dynamic vtable.
561        let mut rjumpv_additional_immediates = 0;
562        // If opcodes is RJUMP, RJUMPI or RJUMPV then this will have absolute jumpdest.
563        let mut absolute_jumpdest = vec![];
564        match op {
565            opcode::RJUMP | opcode::RJUMPI => {
566                let offset = unsafe { read_i16(code.as_ptr().add(i + 1)) } as isize;
567                absolute_jumpdest = vec![offset + 3 + i as isize];
568                // RJUMP is considered a terminating opcode.
569            }
570            opcode::RJUMPV => {
571                // code length for RJUMPV is checked with immediate size.
572                let max_index = code[i + 1] as usize;
573                let len = max_index + 1;
574                // and max_index+1 is to get size of vtable as index starts from 0.
575                rjumpv_additional_immediates = len * 2;
576
577                // +1 is for max_index byte
578                if i + 1 + rjumpv_additional_immediates >= code.len() {
579                    // Malfunctional code RJUMPV vtable is not complete
580                    return Err(EofValidationError::MissingRJUMPVImmediateBytes);
581                }
582
583                // Mark vtable as immediate, max_index was already marked.
584                for imm in 0..rjumpv_additional_immediates {
585                    // SAFETY: immediate size is checked above.
586                    jumps[i + 2 + imm].mark_as_immediate()?;
587                }
588
589                let mut jumps = Vec::with_capacity(len);
590                for vtablei in 0..len {
591                    let offset =
592                        unsafe { read_i16(code.as_ptr().add(i + 2 + 2 * vtablei)) } as isize;
593                    jumps.push(offset + i as isize + 2 + rjumpv_additional_immediates as isize);
594                }
595                absolute_jumpdest = jumps
596            }
597            opcode::CALLF => {
598                let section_i: usize = unsafe { read_u16(code.as_ptr().add(i + 1)) } as usize;
599                let Some(target_types) = types.get(section_i) else {
600                    // code section out of bounds.
601                    return Err(EofValidationError::CodeSectionOutOfBounds);
602                };
603
604                // CALLF operand must not point to to a section with 0x80 as outputs (non-returning)
605                if target_types.is_non_returning() {
606                    return Err(EofValidationError::CALLFNonReturningFunction);
607                }
608                // stack input for this opcode is the input of the called code.
609                stack_requirement = target_types.inputs as i32;
610                // stack diff depends on input/output of the called code.
611                stack_io_diff = target_types.io_diff();
612                // mark called code as accessed.
613                tracker.access_code(section_i);
614
615                // we decrement by `types.inputs` as they are considered as send
616                // to the called code and included in types.max_stack_size.
617                if this_instruction.biggest - stack_requirement + target_types.max_stack_size as i32
618                    > STACK_LIMIT as i32
619                {
620                    // if stack max items + called code max stack size
621                    return Err(EofValidationError::StackOverflow);
622                }
623            }
624            opcode::JUMPF => {
625                let target_index = unsafe { read_u16(code.as_ptr().add(i + 1)) } as usize;
626                // targeted code needs to have zero outputs (be non returning).
627                let Some(target_types) = types.get(target_index) else {
628                    // code section out of bounds.
629                    return Err(EofValidationError::CodeSectionOutOfBounds);
630                };
631
632                // we decrement types.inputs as they are considered send to the called code.
633                // and included in types.max_stack_size.
634                if this_instruction.biggest - target_types.inputs as i32
635                    + target_types.max_stack_size as i32
636                    > STACK_LIMIT as i32
637                {
638                    // stack overflow
639                    return Err(EofValidationError::StackOverflow);
640                }
641                tracker.access_code(target_index);
642
643                if target_types.is_non_returning() {
644                    // if it is not returning
645                    stack_requirement = target_types.inputs as i32;
646                } else {
647                    is_returning = true;
648                    // check if target code produces enough outputs.
649                    if this_types.outputs < target_types.outputs {
650                        return Err(EofValidationError::JUMPFEnoughOutputs);
651                    }
652
653                    stack_requirement = this_types.outputs as i32 + target_types.inputs as i32
654                        - target_types.outputs as i32;
655
656                    // Stack requirement needs to more than this instruction biggest stack number.
657                    if this_instruction.biggest > stack_requirement {
658                        return Err(EofValidationError::JUMPFStackHigherThanOutputs);
659                    }
660
661                    // if this instruction max + target_types max is more then stack limit.
662                    if this_instruction.biggest + stack_requirement > STACK_LIMIT as i32 {
663                        return Err(EofValidationError::StackOverflow);
664                    }
665                }
666            }
667            opcode::EOFCREATE => {
668                let index = code[i + 1] as usize;
669                if index >= num_of_containers {
670                    // code section out of bounds.
671                    return Err(EofValidationError::EOFCREATEInvalidIndex);
672                }
673                tracker.set_subcontainer_type(index, CodeType::ReturnContract)?;
674            }
675            opcode::RETURNCONTRACT => {
676                let index = code[i + 1] as usize;
677                if index >= num_of_containers {
678                    // code section out of bounds.
679                    // TODO custom error
680                    return Err(EofValidationError::EOFCREATEInvalidIndex);
681                }
682                if *tracker
683                    .this_container_code_type
684                    .get_or_insert(CodeType::ReturnContract)
685                    != CodeType::ReturnContract
686                {
687                    // TODO make custom error
688                    return Err(EofValidationError::SubContainerCalledInTwoModes);
689                }
690                tracker.set_subcontainer_type(index, CodeType::ReturnOrStop)?;
691            }
692            opcode::RETURN | opcode::STOP => {
693                if *tracker
694                    .this_container_code_type
695                    .get_or_insert(CodeType::ReturnOrStop)
696                    != CodeType::ReturnOrStop
697                {
698                    return Err(EofValidationError::SubContainerCalledInTwoModes);
699                }
700            }
701            opcode::DATALOADN => {
702                let index = unsafe { read_u16(code.as_ptr().add(i + 1)) } as isize;
703                if data_size < 32 || index > data_size as isize - 32 {
704                    // data load out of bounds.
705                    return Err(EofValidationError::DataLoadOutOfBounds);
706                }
707            }
708            opcode::RETF => {
709                stack_requirement = this_types.outputs as i32;
710                // mark section as returning.
711                is_returning = true;
712
713                if this_instruction.biggest > stack_requirement {
714                    return Err(EofValidationError::RETFBiggestStackNumMoreThenOutputs);
715                }
716            }
717            opcode::DUPN => {
718                stack_requirement = code[i + 1] as i32 + 1;
719            }
720            opcode::SWAPN => {
721                stack_requirement = code[i + 1] as i32 + 2;
722            }
723            opcode::EXCHANGE => {
724                let imm = code[i + 1];
725                let n = (imm >> 4) + 1;
726                let m = (imm & 0x0F) + 1;
727                stack_requirement = n as i32 + m as i32 + 1;
728            }
729            _ => {}
730        }
731        // check if stack requirement is more than smallest stack items.
732        if stack_requirement > this_instruction.smallest {
733            // opcode requirement is more than smallest stack items.
734            return Err(EofValidationError::StackUnderflow);
735        }
736
737        next_smallest = this_instruction.smallest + stack_io_diff;
738        next_biggest = this_instruction.biggest + stack_io_diff;
739
740        // check if jumpdest are correct and mark forward jumps.
741        for absolute_jump in absolute_jumpdest {
742            if absolute_jump < 0 {
743                // jump out of bounds.
744                return Err(EofValidationError::JumpUnderflow);
745            }
746            if absolute_jump >= code.len() as isize {
747                // jump to out of bounds
748                return Err(EofValidationError::JumpOverflow);
749            }
750            // fine to cast as bounds are checked.
751            let absolute_jump = absolute_jump as usize;
752
753            let target_jump = &mut jumps[absolute_jump];
754            if target_jump.is_immediate {
755                // Jump target is immediate byte.
756                return Err(EofValidationError::BackwardJumpToImmediateBytes);
757            }
758
759            // needed to mark forward jumps. It does not do anything for backward jumps.
760            target_jump.is_jumpdest = true;
761
762            if absolute_jump <= i {
763                // backward jumps should have same smallest and biggest stack items.
764                if target_jump.biggest != next_biggest {
765                    // wrong jumpdest.
766                    return Err(EofValidationError::BackwardJumpBiggestNumMismatch);
767                }
768                if target_jump.smallest != next_smallest {
769                    // wrong jumpdest.
770                    return Err(EofValidationError::BackwardJumpSmallestNumMismatch);
771                }
772            } else {
773                // forward jumps can make min even smallest size
774                // while biggest num is needed to check stack overflow
775                target_jump.smallest = core::cmp::min(target_jump.smallest, next_smallest);
776                target_jump.biggest = core::cmp::max(target_jump.biggest, next_biggest);
777            }
778        }
779
780        // additional immediate are from RJUMPV vtable.
781        i += 1 + opcode.immediate_size() as usize + rjumpv_additional_immediates;
782    }
783
784    // error if section is returning but marked as non-returning.
785    if is_returning == this_types.is_non_returning() {
786        // wrong termination.
787        return Err(EofValidationError::NonReturningSectionIsReturning);
788    }
789
790    // last opcode should be terminating
791    if !is_after_termination {
792        // wrong termination.
793        return Err(EofValidationError::LastInstructionNotTerminating);
794    }
795    // TODO integrate max so we dont need to iterate again
796    let mut max_stack_requirement = 0;
797    for opcode in jumps {
798        max_stack_requirement = core::cmp::max(opcode.biggest, max_stack_requirement);
799    }
800
801    if max_stack_requirement != types[this_types_index].max_stack_size as i32 {
802        // stack overflow
803        return Err(EofValidationError::MaxStackMismatch);
804    }
805
806    Ok(())
807}
808
809#[cfg(test)]
810mod test {
811    use super::*;
812    use revm_primitives::hex;
813
814    #[test]
815    fn test1() {
816        // result:Result { result: false, exception: Some("EOF_ConflictingStackHeight") }
817        let err =
818            validate_raw_eof(hex!("ef0001010004020001000704000000008000016000e200fffc00").into());
819        assert!(err.is_err(), "{err:#?}");
820    }
821
822    #[test]
823    fn test2() {
824        // result:Result { result: false, exception: Some("EOF_InvalidNumberOfOutputs") }
825        let err =
826            validate_raw_eof_inner(hex!("ef000101000c02000300040004000204000000008000020002000100010001e30001005fe500025fe4").into(),None);
827        assert!(err.is_ok(), "{err:#?}");
828    }
829
830    #[test]
831    fn test3() {
832        // result:Result { result: false, exception: Some("EOF_InvalidNumberOfOutputs") }
833        let err =
834            validate_raw_eof_inner(hex!("ef000101000c02000300040008000304000000008000020002000503010003e30001005f5f5f5f5fe500025050e4").into(),None);
835        assert_eq!(
836            err,
837            Err(EofError::Validation(
838                EofValidationError::JUMPFStackHigherThanOutputs
839            ))
840        );
841    }
842
843    #[test]
844    fn test4() {
845        //0xef0001010004020001000e04000000008000045f6000e100025f5f6000e1fffd00
846        // result:Result { result: false, exception: Some("EOF_InvalidNumberOfOutputs") }
847        let err = validate_raw_eof(
848            hex!("ef0001010004020001000e04000000008000045f6000e100025f5f6000e1fffd00").into(),
849        );
850        assert_eq!(
851            err,
852            Err(EofError::Validation(
853                EofValidationError::BackwardJumpBiggestNumMismatch
854            ))
855        );
856    }
857
858    #[test]
859    fn test5() {
860        let err = validate_raw_eof(hex!("ef000101000402000100030400000000800000e5ffff").into());
861        assert_eq!(
862            err,
863            Err(EofError::Validation(
864                EofValidationError::CodeSectionOutOfBounds
865            ))
866        );
867    }
868
869    #[test]
870    fn size_limit() {
871        let eof = validate_raw_eof_inner(
872            hex!("ef00010100040200010003040001000080000130500000").into(),
873            Some(CodeType::ReturnOrStop),
874        );
875        assert!(eof.is_ok());
876    }
877
878    #[test]
879    fn test() {
880        let eof = validate_raw_eof_inner(
881            hex!("ef0001010004020001000504ff0300008000023a60cbee1800").into(),
882            None,
883        );
884        assert_eq!(
885            eof,
886            Err(EofError::Validation(EofValidationError::DataNotFilled))
887        );
888    }
889
890    #[test]
891    fn unreachable_code_section() {
892        let eof = validate_raw_eof_inner(
893            hex!("ef000101000c02000300030001000304000000008000000080000000800000e50001fee50002")
894                .into(),
895            None,
896        );
897        assert_eq!(
898            eof,
899            Err(EofError::Validation(
900                EofValidationError::CodeSectionNotAccessed
901            ))
902        );
903    }
904
905    #[test]
906    fn non_returning_sections() {
907        let eof = validate_raw_eof_inner(
908            hex!("ef000101000c02000300040001000304000000008000000080000000000000e300020000e50001")
909                .into(),
910            Some(CodeType::ReturnOrStop),
911        );
912        assert_eq!(
913            eof,
914            Err(EofError::Validation(
915                EofValidationError::NonReturningSectionIsReturning
916            ))
917        );
918    }
919
920    #[test]
921    fn incompatible_container_kind() {
922        let eof = validate_raw_eof_inner(
923            hex!("ef000101000402000100060300010014040000000080000260006000ee00ef00010100040200010001040000000080000000")
924                .into(),
925            Some(CodeType::ReturnOrStop),
926        );
927        assert_eq!(
928            eof,
929            Err(EofError::Validation(
930                EofValidationError::SubContainerCalledInTwoModes
931            ))
932        );
933    }
934}
revm_interpreter/interpreter/analysis.rs

revm_interpreter/interpreter/
analysis.rs
