vnf,runrom: detect bad data access

This includes detection for:

- Stack underflows (it was theoretically already there but it had never
  been properly tested).
- Load/store out of bounds for a given variable known via the .nasm/
  directory.
- Load out of bounds on a set of data referenced via a raw label (see
  commit aa5174fc055d ("xixanta: Add an hint for the ending of data
  labels")).

Signed-off-by: Miquel Sabaté Solà <mssola@mssola.com>

10 files changed, 259 insertions, 6 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 253d988..36a898e 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -95,6 +95,7 @@ version = "0.1.0"
 dependencies = [
  "header",
  "vnf",
+ "xixanta",
 ]
 
 [[package]]
diff --git a/crates/runrom/Cargo.toml b/crates/runrom/Cargo.toml
index e1c70fc..25badd0 100644
--- a/crates/runrom/Cargo.toml
+++ b/crates/runrom/Cargo.toml
@@ -7,4 +7,5 @@ authors.workspace = true
 
 [dependencies]
 header.workspace = true
-vnf.workspace = true
\ No newline at end of file
+vnf.workspace = true
+xixanta.workspace = true
\ No newline at end of file
diff --git a/crates/runrom/src/main.rs b/crates/runrom/src/main.rs
index 4d94384..00879d0 100644
--- a/crates/runrom/src/main.rs
+++ b/crates/runrom/src/main.rs
@@ -4,6 +4,7 @@ use std::fs::File;
 use std::io::{BufRead, BufReader, ErrorKind, Read, Seek, SeekFrom};
 use std::path::{Path, PathBuf};
 use vnf::{Machine, MemoryPolicy};
+use xixanta::assembler::Range;
 
 /// Version for this program.
 const VERSION: &str = "0.1.0";
@@ -300,6 +301,69 @@ fn start_from_reset_vector(file: &String) -> u16 {
     ((buf[1] as u16) << 8) + buf[0] as u16
 }
 
+fn fetch_memory_addresses(nasm: Option<PathBuf>) -> Result<(Vec<Range>, Option<usize>), String> {
+    let mut memories = vec![];
+    let mut stack = None;
+
+    let Some(path) = nasm else {
+        return Ok((memories, stack));
+    };
+
+    if let Ok(file) = File::open(path.clone().join("memory.txt")) {
+        let reader = BufReader::new(file);
+        for line in reader.lines() {
+            let line = line.map_err(|e| e.to_string())?;
+            if line.is_empty() || line.starts_with("---") {
+                break;
+            }
+
+            let (left, right) = line.split_once(':').unwrap();
+            let (start, end) = match left.trim().split_once('-') {
+                Some((start, end)) => (
+                    usize::from_str_radix(start.get(1..).unwrap(), 16).unwrap(),
+                    usize::from_str_radix(end.get(1..).unwrap(), 16).unwrap() + 1,
+                ),
+                None => (
+                    usize::from_str_radix(left.get(1..).unwrap(), 16).unwrap(),
+                    usize::from_str_radix(left.get(1..).unwrap(), 16).unwrap() + 1,
+                ),
+            };
+
+            let name = right.trim().to_string();
+            if name == "<stack>" {
+                stack = Some(start);
+            }
+
+            memories.push(Range {
+                range: std::ops::Range { start, end },
+                name,
+            });
+        }
+    }
+
+    if let Ok(file) = File::open(path.join("addresses.txt")) {
+        let reader = BufReader::new(file);
+        for line in reader.lines() {
+            let line = line.map_err(|e| e.to_string())?;
+            let columns: Vec<&str> = line.split(',').map(|s| s.trim()).collect();
+            if columns.len() != 3 {
+                return Err("badly formatted address file".to_string());
+            }
+
+            let start = usize::from_str_radix(columns[1], 16)
+                .map_err(|_| format!("invalid hex value: '{}'", columns[1]))?;
+            let end = usize::from_str_radix(columns[2], 16)
+                .map_err(|_| format!("invalid hex value: '{}'", columns[2]))?;
+            memories.push(Range {
+                range: std::ops::Range { start, end },
+                name: columns[0].to_string(),
+            });
+        }
+    }
+
+    Ok((memories, stack))
+}
+
 fn run(
     file: &Path,
     start: u16,
@@ -307,14 +371,22 @@ fn run(
     assume_function: bool,
     halt_on_brk: bool,
     cycle_limit: Option<usize>,
+    nasm: Option<PathBuf>,
     dump_memory: bool,
 ) -> Result<(), String> {
-    let mut machine = Machine::from(file, start, MemoryPolicy::default())?;
+    let (addresses, stack) = fetch_memory_addresses(nasm)?;
+
+    let mut policy = MemoryPolicy::default();
+    if let Some(stack) = stack {
+        policy.minimum_stack_value = stack as u8;
+    }
 
+    let mut machine = Machine::from(file, start, policy)?;
     machine.verbose = true;
     machine.run_function_mode = assume_function;
     machine.halt_on_brk = halt_on_brk;
     machine.cycle_limit = cycle_limit;
+    machine.addresses = addresses;
 
     machine.until_address(end)?;
 
@@ -361,6 +433,7 @@ fn main() {
         args.assume_function,
         args.halt_on_brk,
         args.cycle_limit,
+        args.nasm,
         args.dump_memory,
     ) {
         Ok(m) => m,
diff --git a/lib/vnf/src/lib.rs b/lib/vnf/src/lib.rs
index e5e280a..a6e9b62 100644
--- a/lib/vnf/src/lib.rs
+++ b/lib/vnf/src/lib.rs
@@ -400,6 +400,11 @@ pub struct Machine {
     /// The maximum amount of cycles that the machine should reach before
     /// halting.
     pub cycle_limit: Option<usize>,
+
+    /// List of addresses for which we have information on their upper and lower
+    /// bounds. This is used to detect overflows/underflows and any kind of bad
+    /// indexed access.
+    pub addresses: Vec<xixanta::assembler::Range>,
 }
 
 // On success, returns a vector of MemoryCell representing the RAM for a
@@ -516,6 +521,7 @@ impl Machine {
             joypads: [Joypad::default(), Joypad::default()],
             halt_on_brk: true,
             cycle_limit: None,
+            addresses: vec![],
         })
     }
 
@@ -768,7 +774,13 @@ impl Machine {
     /// Run until the program counter reaches the given 'address'.
     pub fn until_address(&mut self, address: u16) -> Result<(), String> {
         while self.pc != address as usize && self.active {
-            self.next_iteration()?;
+            if let Err(e) = self.next_iteration() {
+                if self.verbose {
+                    println!("\n@:");
+                    self.report();
+                }
+                return Err(e);
+            }
         }
 
         Ok(())
@@ -833,7 +845,7 @@ impl Machine {
 
         // And update the stack pointer if possible.
         self.s -= 1;
-        if self.s == self.policy.minimum_stack_value {
+        if self.s < self.policy.minimum_stack_value {
             return Err("stack underflow!".to_string());
         }
 
@@ -1422,6 +1434,51 @@ impl Machine {
         Ok(byte)
     }
 
+    // Given an address, try to fetch its range as it may appear in
+    // 'self.addresses'. This function will make a best effort to pick a Range
+    // if two or more appear to overlap.
+    fn fetch_address_range(&mut self, address: usize) -> Option<&xixanta::assembler::Range> {
+        let mut ret: Option<&xixanta::assembler::Range> = None;
+
+        for mr in &self.addresses {
+            if mr.range.contains(&address) {
+                if let Some(existing) = ret {
+                    // If there is already a range that was picked, discard
+                    // whichever is furthest from the start. Typically this
+                    // happens in subroutines with data labels within it. In
+                    // this case both the subroutine and the data label will
+                    // overlap, but if the address is closest to the data label,
+                    // then we can safely assume that it's the data label being
+                    // referenced.
+                    if existing.range.start > mr.range.start {
+                        continue;
+                    }
+                }
+                ret = Some(mr);
+            }
+        }
+        ret
+    }
+
+    // Returns the address pointed by the current instruction's value plus the
+    // given index while making sure that the final address does not reach out
+    // of bounds if it's a known address range.
+    fn safe_indexed_address(&mut self, index: usize) -> Result<usize, String> {
+        let base = self.current_instruction.value();
+        let target = base + index;
+
+        if let Some(range) = self.fetch_address_range(base)
+            && !range.range.contains(&target)
+        {
+            return Err(format!(
+                "out of bounds: indexed access to ${:04X} falls out of '{}' \
+                     (${:02X}-${:02X}; bounded inclusively below and exclusively above)",
+                target, range.name, range.range.start, range.range.end
+            ));
+        }
+        Ok(target)
+    }
+
     // Returns the effective address which the current instruction is
     // targetting.
     fn target_address(&mut self) -> Result<usize, String> {
@@ -1430,10 +1487,10 @@ impl Machine {
                 Ok(self.current_instruction.value())
             }
             AddressingMode::ZeropageIndexedX | AddressingMode::IndexedX => {
-                Ok(self.current_instruction.value() + self.x as usize)
+                self.safe_indexed_address(self.x as usize)
             }
             AddressingMode::ZeropageIndexedY | AddressingMode::IndexedY => {
-                Ok(self.current_instruction.value() + self.y as usize)
+                self.safe_indexed_address(self.y as usize)
             }
             AddressingMode::IndirectY => {
                 let ptr = self.current_instruction.value() as u16;
diff --git a/scripts/test-e2e.sh b/scripts/test-e2e.sh
index 0cf37f0..17766a4 100755
--- a/scripts/test-e2e.sh
+++ b/scripts/test-e2e.sh
@@ -351,6 +351,25 @@ exit_code=$((exit_code + $?))
 diff tests/out/misc-foo.txt tests/expected/runrom/misc-foo.txt
 exit_code=$((exit_code + $?))
 
+echo "test: runrom => overflows.nes"
+./target/debug/nasm -Werror --asan --write-info --out tests/out/overflows.nes tests/runrom/overflows.s
+
+./target/debug/runrom --nasm .nasm/ --dump-memory --function tests/out/overflows.nes &> tests/out/overflow-reset.txt
+diff tests/out/overflow-reset.txt tests/expected/runrom/overflow-reset.txt
+exit_code=$((exit_code + $?))
+
+./target/debug/runrom --nasm .nasm/ --dump-memory --function --start overflow_on_arithmetics tests/out/overflows.nes &> tests/out/overflow-arithmetics.txt
+diff tests/out/overflow-arithmetics.txt tests/expected/runrom/overflow-arithmetics.txt
+exit_code=$((exit_code + $?))
+
+./target/debug/runrom --nasm .nasm/ --dump-memory --function --start stack_underflow tests/out/overflows.nes &> tests/out/overflow-stack.txt
+diff tests/out/overflow-stack.txt tests/expected/runrom/overflow-stack.txt
+exit_code=$((exit_code + $?))
+
+./target/debug/runrom --nasm .nasm/ --dump-memory --function --start bad_rom_data_indexing tests/out/overflows.nes &> tests/out/overflow-data-indexing.txt
+diff tests/out/overflow-data-indexing.txt tests/expected/runrom/overflow-data-indexing.txt
+exit_code=$((exit_code + $?))
+
 ##
 # vnf-tests
 
diff --git a/tests/expected/runrom/overflow-arithmetics.txt b/tests/expected/runrom/overflow-arithmetics.txt
new file mode 100644
index 0000000..3eadfae
--- /dev/null
+++ b/tests/expected/runrom/overflow-arithmetics.txt
@@ -0,0 +1,6 @@
+<start>		PC: $8011, cycles: 7, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----I--
+ldx #$01	PC: $8013, cycles: 9, registers: [a: $00, x: $01, y: $00, sp: $FD], status: ----I--
+
+@:
+lda $0F, x	PC: $8013, cycles: 9, registers: [a: $00, x: $01, y: $00, sp: $FD], status: ----I--
+error: out of bounds: indexed access to $0010 falls out of 'zp_buffer' ($00-$10; bounded inclusively below and exclusively above)
diff --git a/tests/expected/runrom/overflow-data-indexing.txt b/tests/expected/runrom/overflow-data-indexing.txt
new file mode 100644
index 0000000..469a265
--- /dev/null
+++ b/tests/expected/runrom/overflow-data-indexing.txt
@@ -0,0 +1,10 @@
+<start>		PC: $801B, cycles: 7, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----I--
+ldx #$00	PC: $801D, cycles: 9, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+lda $8028, x	PC: $8020, cycles: 13, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+clc		PC: $8021, cycles: 15, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+adc #$04	PC: $8023, cycles: 17, registers: [a: $04, x: $00, y: $00, sp: $FD], status: ----I--
+tax		PC: $8024, cycles: 19, registers: [a: $04, x: $04, y: $00, sp: $FD], status: ----I--
+
+@:
+lda $8028, x	PC: $8024, cycles: 19, registers: [a: $04, x: $04, y: $00, sp: $FD], status: ----I--
+error: out of bounds: indexed access to $802C falls out of 'bad_rom_data_indexing::data' ($8028-$802C; bounded inclusively below and exclusively above)
diff --git a/tests/expected/runrom/overflow-reset.txt b/tests/expected/runrom/overflow-reset.txt
new file mode 100644
index 0000000..6097a9c
--- /dev/null
+++ b/tests/expected/runrom/overflow-reset.txt
@@ -0,0 +1,8 @@
+<start>		PC: $8000, cycles: 7, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----I--
+ldx #$00	PC: $8002, cycles: 9, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+lda $00, x	PC: $8004, cycles: 13, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+dex		PC: $8005, cycles: 15, registers: [a: $00, x: $FF, y: $00, sp: $FD], status: ----I--
+
+@:
+lda $00, x	PC: $8005, cycles: 15, registers: [a: $00, x: $FF, y: $00, sp: $FD], status: ----I--
+error: out of bounds: indexed access to $00FF falls out of 'zp_buffer' ($00-$10; bounded inclusively below and exclusively above)
diff --git a/tests/expected/runrom/overflow-stack.txt b/tests/expected/runrom/overflow-stack.txt
new file mode 100644
index 0000000..3a00e0a
--- /dev/null
+++ b/tests/expected/runrom/overflow-stack.txt
@@ -0,0 +1,6 @@
+<start>		PC: $8016, cycles: 7, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----I--
+lda #$00	PC: $8018, cycles: 9, registers: [a: $00, x: $00, y: $00, sp: $FD], status: ----IZ-
+
+@:
+pha		PC: $8018, cycles: 9, registers: [a: $00, x: $00, y: $00, sp: $FC], status: ----IZ-
+error: stack underflow!
diff --git a/tests/runrom/overflows.s b/tests/runrom/overflows.s
new file mode 100644
index 0000000..e2a5b47
--- /dev/null
+++ b/tests/runrom/overflows.s
@@ -0,0 +1,72 @@
+.segment "HEADER"
+    .byte 'N', 'E', 'S', $1A
+    .byte $02, $01
+    .byte $00
+    .byte $00
+
+.segment "CHARS"
+.byte 0
+
+.segment "VECTORS"
+    .addr reset, reset, reset
+
+.segment "CODE"
+
+zp_buffer = $00                 ; asan:reserve $10
+
+.proc reset
+    ;; Fine.
+    ldx #0
+    lda zp_buffer, x
+
+    ;; NOTE: overflow!
+    dex
+    lda zp_buffer, x
+
+    ;; Just so there are no "unused" warnings :)
+    jsr overflow_on_arithmetics
+    jsr stack_underflow
+    jsr bad_rom_data_indexing
+
+    rts
+.endproc
+
+.proc overflow_on_arithmetics
+    ;; NOTE: overflow!
+    ;; NOTE: another overflow scenario could be 'lda zp_buffer + 16, x', but
+    ;; 'nasm' can statically point this out and it will throw an error.
+    ldx #1
+    lda zp_buffer + 15, x
+
+    rts
+.endproc
+
+;; asan:stack $FD-$FF
+.proc stack_underflow
+    lda #0
+
+    ;; NOTE: stack underflow!
+    pha
+    pla
+
+    rts
+.endproc
+
+.proc bad_rom_data_indexing
+    ;; Fine.
+    ldx #0
+    lda data, x
+
+    clc
+    adc #4
+    tax
+
+    ;; NOTE: overflow!
+    lda data, x
+
+    rts
+data:
+    .byte $00, $01, $02, $03
+
+    lda zp_buffer
+.endproc