`singly_ll_pointers::List::{iter, iter_mut}` can cause use-after-free.

### **Description**:

`algorithmica::ll::singly_ll_pointers::List::iter` and `List::iter_mut` can return iterators that outlive the list they borrow from.

This allows safe Rust code to access nodes after the list has been dropped, causing heap-use-after-free. `iter_mut` can additionally produce a mutable reference to freed memory. The linked-list module is publicly exported through `algorithmica::ll::singly_ll_pointers`, and these APIs are not marked `unsafe`.

### **Environment**:

algorithmica version: 0.1.10
rustc version: 1.94.1
OS: Ubuntu 20.04.6 LTS

Command:
```
RUSTFLAGS="-Z sanitizer=address" cargo +nightly run --target x86_64-unknown-linux-gnu
```

### PoC 1: `iter`

```rust
extern crate algorithmica;

fn main() {
    let mut iter = {
        let mut list = algorithmica::ll::singly_ll_pointers::List::new();
        list.push_front("hello".to_string());
        list.iter()
    };
    assert_eq!(iter.next(), Some(&"hello".to_string()));
}
```

### PoC 2: `iter_mut`

```
extern crate algorithmica;

fn main() {
    let mut iter = {
        let mut list = algorithmica::ll::singly_ll_pointers::List::new();
        list.push_front("hello".to_string());
        list.iter_mut()
    };

    if let Some(value) = iter.next() {
        value.push_str(" world");
        println!("{:?}", value);
    }
}
```

### **Expected behavior:**

Safe Rust code should not be able to access freed memory.

A correctly implemented iterator API should make both PoCs fail to compile because the returned iterator borrows from `list`, but `list` is dropped at the end of the inner block.

Expected compiler behavior would be similar to:

```
error[E0597]: `list` does not live long enough
```

### **Actual behavior**

Both PoCs compile successfully.

With AddressSanitizer, `iter` reports a heap-use-after-free:

```
==78218==ERROR: AddressSanitizer: heap-use-after-free on address 0x7b3256ce0058 at pc 0x56406dec412b bp 0x7fffbee74d40 sp 0x7fffbee74d38
READ of size 8 at 0x7b3256ce0058 thread T0
    #0 0x56406dec412a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10212a) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #1 0x56406dec39a0  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x1019a0) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #2 0x56406dec495d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10295d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #3 0x56406dec5083  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x103083) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #4 0x56406dec333a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10133a) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #5 0x56406dec394d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10194d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #6 0x56406dec4e70  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102e70) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #7 0x56406deebe85  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x129e85) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #8 0x56406dec4ddf  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102ddf) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #9 0x56406dec527d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10327d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #10 0x7f02577f3082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082) (BuildId: 5792732f783158c66fb4f3756458ca24e46e827d)
    #11 0x56406de08e9d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x46e9d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)

0x7b3256ce0058 is located 24 bytes inside of 32-byte region [0x7b3256ce0040,0x7b3256ce0060)
freed by thread T0 here:
    #0 0x56406de94816  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd2816) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #1 0x56406dec554b  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10354b) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #2 0x56406dec31fa  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x1011fa) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #3 0x56406dec2ff9  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x100ff9) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #4 0x56406dec333a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10133a) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #5 0x56406dec4ddf  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102ddf) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #6 0x56406dec527d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10327d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)

previously allocated by thread T0 here:
    #0 0x56406de94ab4  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0xd2ab4) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #1 0x56406dec534f  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10334f) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #2 0x56406dec503b  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10303b) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #3 0x56406dec333a  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10133a) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #4 0x56406dec4ddf  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x102ddf) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)
    #5 0x56406dec527d  (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10327d) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be)

SUMMARY: AddressSanitizer: heap-use-after-free (/Rust-Lib-Testing/test/tests/replay/algorithmica-0.1.10/replay_algorithmica2/target/x86_64-unknown-linux-gnu/debug/replay_algorithmica2+0x10212a) (BuildId: e340ca06be2e17e75be9a04f385650dd601203be) 
Shadow bytes around the buggy address:
  0x7b3256cdfd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b3256cdfe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b3256cdfe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b3256cdff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x7b3256cdff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x7b3256ce0000: fa fa fd fd fd fd fa fa fd fd fd[fd]fa fa fa fa
  0x7b3256ce0080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x7b3256ce0100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x7b3256ce0180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x7b3256ce0200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x7b3256ce0280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==78218==ABORTING
```

`iter_mut` can also access freed memory, and may report heap-use-after-free when the returned mutable reference is used.

```
==8468==ERROR: AddressSanitizer: heap-use-after-free on address 0x7c1b302e0058at pc 0x55da3b0b0a5b bp 0x7fff313e7700 sp 0x7fff313e76f8
```

### **Root cause**:

These issues are in `src/ll/singly_ll_pointers.rs`.

The iterator types store references to internal list nodes:

https://github.com/AbrarNitk/algorithmica/blob/fa2f6914e61cf37a0876b0673abf1fd0aaf50d48/algorithmica/src/ll/singly_ll_pointers.rs#L61-L65

https://github.com/AbrarNitk/algorithmica/blob/fa2f6914e61cf37a0876b0673abf1fd0aaf50d48/algorithmica/src/ll/singly_ll_pointers.rs#L67-L71

The lifetime `'a` is not tied to the lifetime of `&self` or `&mut self`. This allows the returned iterator to outlive the list. When the list is dropped, its nodes are freed. After that, the escaped iterator still points to the freed node. Calling `next()` dereferences it.

### Possible Fix

Tie the returned iterator lifetime to the borrow of the list:

```
pub fn iter(&self) -> Iter<'_, Item> {
    Iter {
        current: unsafe { self.head.as_ref() },
    }
}

pub fn iter_mut(&mut self) -> IterMut<'_, Item> {
    IterMut {
        current: unsafe { self.head.as_mut() },
    }
}
```

After these change, both PoCs should fail to compile, which is the correct behavior.

If these sounds reasonable, I would be happy to open a PR to fix these issues.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

`singly_ll_pointers::List::{iter, iter_mut}` can cause use-after-free. #9

Description:

Environment:

PoC 1: `iter`

PoC 2: `iter_mut`

Expected behavior:

Actual behavior

Root cause:

Possible Fix

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	pub fn iter<'a>(&self) -> Iter<'a, Item> {
	Iter {
	current: unsafe { self.head.as_ref() },
	}
	}

	pub fn iter_mut<'a>(&mut self) -> IterMut<'a, Item> {
	IterMut {
	current: unsafe { self.head.as_mut() },
	}
	}

singly_ll_pointers::List::{iter, iter_mut} can cause use-after-free. #9

Description

Description:

Environment:

PoC 1: iter

PoC 2: iter_mut

Expected behavior:

Actual behavior

Root cause:

Possible Fix

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

`singly_ll_pointers::List::{iter, iter_mut}` can cause use-after-free. #9

PoC 1: `iter`

PoC 2: `iter_mut`