| 1 |
use crate::{tags::IfdPointer, TiffError, TiffFormatError}; |
| 2 |
use std::collections::HashMap; |
| 3 |
|
| 4 |
/// The IFD structure of a TIFF file should be limited to a forest of entries, and a tree when we |
| 5 |
/// only consider having a primary IFD and its children. There is up to one primary child of a node |
| 6 |
/// that is the `next` entry in an IFD itself. Since we offer iteration over this chain we want to |
| 7 |
/// detect when a new edge would introduce a cycle, such that callers can be guaranteed to |
| 8 |
/// terminate iteration at some point even in malicious images. |
| 9 |
/// |
| 10 |
/// However, we are not necessarily visiting the IFDs in their topological order. |
| 11 |
/// |
| 12 |
/// Since we only consider one child, we run union find to assign each pointer to a known chain. |
| 13 |
/// Then, when we insert a new edge we check if they belong to the same component. |
| 14 |
#[derive(Default, Debug)] |
| 15 |
pub struct IfdCycles { |
| 16 |
/// The root of each component union. |
| 17 |
component_union: HashMap<ComponentId, ComponentId>, |
| 18 |
links: HashMap<IfdPointer, u64>, |
| 19 |
chains: HashMap<IfdPointer, ComponentId>, |
| 20 |
} |
| 21 |
|
| 22 |
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] |
| 23 |
struct ComponentId(u64); |
| 24 |
|
| 25 |
impl IfdCycles { |
| 26 |
pub fn new() -> Self { |
| 27 |
IfdCycles::default() |
| 28 |
} |
| 29 |
|
| 30 |
pub fn insert_next( |
| 31 |
&mut self, |
| 32 |
from: IfdPointer, |
| 33 |
to: Option<IfdPointer>, |
| 34 |
) -> Result<bool, TiffError> { |
| 35 |
let to_offset = to.map_or(0, |p| p.0); |
| 36 |
|
| 37 |
// For some reason we got |
| 38 |
match self.links.get(&from) { |
| 39 |
Some(existing) if *existing == to_offset => return Ok(false), |
| 40 |
// We got here twice with two different reads of the same IFD. That is .. unusual and |
| 41 |
// we interpret it as a cycle. |
| 42 |
Some(_) => return Err(TiffError::FormatError(TiffFormatError::CycleInOffsets)), |
| 43 |
None => self.links.insert(from, to_offset), |
| 44 |
}; |
| 45 |
|
| 46 |
self.ensure_node(from); |
| 47 |
|
| 48 |
if let Some(to) = to { |
| 49 |
self.ensure_node(to); |
| 50 |
|
| 51 |
let parent = self.nominal_component(from); |
| 52 |
let child = self.nominal_component(to); |
| 53 |
|
| 54 |
if parent == child { |
| 55 |
return Err(TiffError::FormatError(TiffFormatError::CycleInOffsets)); |
| 56 |
} |
| 57 |
|
| 58 |
self.component_union.insert(child, parent); |
| 59 |
} |
| 60 |
|
| 61 |
Ok(true) |
| 62 |
} |
| 63 |
|
| 64 |
fn ensure_node(&mut self, ifd: IfdPointer) { |
| 65 |
self.chains.entry(ifd).or_insert_with(|| { |
| 66 |
let id = ComponentId(self.component_union.len() as u64); |
| 67 |
self.component_union.insert(id, id); |
| 68 |
id |
| 69 |
}); |
| 70 |
} |
| 71 |
|
| 72 |
fn nominal_component(&mut self, node: IfdPointer) -> ComponentId { |
| 73 |
let id = self.chains[&node]; |
| 74 |
|
| 75 |
let nomimal = { |
| 76 |
let mut iter = id; |
| 77 |
|
| 78 |
loop { |
| 79 |
let parent = self.component_union[&iter]; |
| 80 |
|
| 81 |
if parent == iter { |
| 82 |
break parent; |
| 83 |
} |
| 84 |
|
| 85 |
iter = parent; |
| 86 |
} |
| 87 |
}; |
| 88 |
|
| 89 |
if nomimal != id { |
| 90 |
// Compress. |
| 91 |
let mut iter = id; |
| 92 |
|
| 93 |
loop { |
| 94 |
let parent = self.component_union[&iter]; |
| 95 |
|
| 96 |
if parent == iter { |
| 97 |
break; |
| 98 |
} |
| 99 |
|
| 100 |
self.component_union.insert(iter, nomimal); |
| 101 |
iter = parent; |
| 102 |
} |
| 103 |
} |
| 104 |
|
| 105 |
nomimal |
| 106 |
} |
| 107 |
} |
| 108 |
|
| 109 |
#[test] |
| 110 |
fn cycles_are_detected() { |
| 111 |
let mut cycles = IfdCycles::new(); |
| 112 |
|
| 113 |
cycles |
| 114 |
.insert_next(IfdPointer(0x20), Some(IfdPointer(0x800))) |
| 115 |
.expect("non-existing link is valid"); |
| 116 |
|
| 117 |
cycles |
| 118 |
.insert_next(IfdPointer(0x800), Some(IfdPointer(0x20))) |
| 119 |
.expect_err("cycle must be detected"); |
| 120 |
} |
| 121 |
|
| 122 |
#[test] |
| 123 |
fn reflective_cycle() { |
| 124 |
let mut cycles = IfdCycles::new(); |
| 125 |
|
| 126 |
cycles |
| 127 |
.insert_next(IfdPointer(0x20), Some(IfdPointer(0x20))) |
| 128 |
.expect_err("self-referential cycle must be detected"); |
| 129 |
} |
| 130 |
|
| 131 |
#[test] |
| 132 |
fn late_cycle() { |
| 133 |
let mut cycles = IfdCycles::new(); |
| 134 |
|
| 135 |
cycles |
| 136 |
.insert_next(IfdPointer(0x20), Some(IfdPointer(0x40))) |
| 137 |
.expect("non-existing link is valid"); |
| 138 |
|
| 139 |
cycles |
| 140 |
.insert_next(IfdPointer(0x60), Some(IfdPointer(0x80))) |
| 141 |
.expect("non-existing link is valid"); |
| 142 |
cycles |
| 143 |
.insert_next(IfdPointer(0x80), Some(IfdPointer(0x20))) |
| 144 |
.expect("non-existing link is valid"); |
| 145 |
|
| 146 |
cycles |
| 147 |
.insert_next(IfdPointer(0x40), Some(IfdPointer(0x60))) |
| 148 |
.expect_err("non-existing link is valid"); |
| 149 |
} |
| 150 |
|
| 151 |
#[test] |
| 152 |
fn odd_cycle() { |
| 153 |
let mut cycles = IfdCycles::new(); |
| 154 |
|
| 155 |
cycles |
| 156 |
.insert_next(IfdPointer(0x20), Some(IfdPointer(0x40))) |
| 157 |
.expect("non-existing link is valid"); |
| 158 |
|
| 159 |
cycles |
| 160 |
.insert_next(IfdPointer(0x60), Some(IfdPointer(0x80))) |
| 161 |
.expect("non-existing link is valid"); |
| 162 |
cycles |
| 163 |
.insert_next(IfdPointer(0x80), Some(IfdPointer(0x20))) |
| 164 |
.expect("non-existing link is valid"); |
| 165 |
|
| 166 |
cycles |
| 167 |
.insert_next(IfdPointer(0x40), Some(IfdPointer(0x80))) |
| 168 |
.expect_err("non-existing link is valid"); |
| 169 |
} |