Merge branch 'main' into fix/sec-rels-decompression-budget

apps/gridcraft-cli/src/check/package.rs

@@ -6,6 +6,10 @@ const MAX_XML_PART: u64 = 64 * 1024 * 1024;
 /// Most zip entries looked at while validating a written package.
 const MAX_ENTRIES: usize = 200_000;
 
+/// Decompressed bytes that comparing one package's relationship kinds may read in total: the
+/// relationship parts themselves and the targets whose content is checked.
+const RELATIONSHIP_BUDGET: u64 = 512 * 1024 * 1024;
+
 /// Relationship kinds (lower case) whose absence after a save isn't a loss: the calculation chain is
 /// a cache Excel rebuilds, and GridCraft never writes it.
 pub(super) const REBUILT_KINDS: [&str; 1] = ["calcchain"];
@@ -117,6 +121,30 @@ fn read_zip_part(zip: &mut Zip<'_>, name: &str) -> Result<Vec<u8>, String> {
     Ok(buf)
 }
 
+enum PartError {
+    /// Reading the part would spend more than the remaining budget.
+    OverBudget,
+    Unreadable,
+}
+
+/// Reads a part like [`read_zip_part`], charging the decompressed bytes to `budget`.
+fn read_zip_part_within(zip: &mut Zip<'_>, name: &str, budget: &mut u64) -> Result<Vec<u8>, PartError> {
+    let f = zip.by_name(name).map_err(|_| PartError::Unreadable)?;
+    // One byte past what is left shows that the part doesn't fit.
+    let limit = MAX_XML_PART.min(budget.saturating_add(1));
+    let mut buf = Vec::new();
+    // Bytes read before a decompression error still count against the budget.
+    let res = f.take(limit).read_to_end(&mut buf);
+    let read = buf.len() as u64;
+    if read > *budget {
+        *budget = 0;
+        return Err(PartError::OverBudget);
+    }
+    *budget -= read;
+    res.map_err(|_| PartError::Unreadable)?;
+    Ok(buf)
+}
+
 /// Whether the producer flagged its cached results as stale with `<calcPr fullCalcOnLoad="1">`:
 /// libraries that don't calculate write it, and store 0 or nothing as every formula's value.
 pub(super) fn full_calc_on_load(bytes: &[u8]) -> bool {
@@ -232,19 +260,30 @@ pub fn validate_package(bytes: &[u8]) -> Result<Vec<String>, String> {
 /// nothing are left out, as a save may rightly drop them: a link to a place in the workbook
 /// (`#Sheet1!A1`, written as a cell's `location`) and a target part with nothing in it.
 pub(super) fn relationship_kinds(bytes: &[u8]) -> Result<BTreeMap<String, String>, String> {
+    relationship_kinds_within(bytes, RELATIONSHIP_BUDGET)
+}
+
+/// [`relationship_kinds`] reading at most `budget` decompressed bytes. `Err` once the relationship
+/// parts alone need more: their kinds can't be listed completely.
+fn relationship_kinds_within(bytes: &[u8], mut budget: u64) -> Result<BTreeMap<String, String>, String> {
     let mut zip = zip::ZipArchive::new(Cursor::new(bytes)).map_err(|e| format!("not a zip package: {e}"))?;
     let names = zip_names(&mut zip);
     let by_key: HashMap<String, &String> = names.iter().map(|n| (part_key(n), n)).collect();
     // Several relationships name the same part; each fresh check decompressed it again, so
     // repeated references to one highly compressible part multiplied the work. The verdict is
     // remembered per (part, named content) and the decompression the package can cause is
-    // budgeted as a whole (finding: repeated decompression).
+    // budgeted as a whole, the relationship parts included: many large, unreferenced rels parts
+    // would otherwise each spend a full per-part allowance.
     let mut verdicts: HashMap<(String, &'static str), bool> = HashMap::new();
-    let mut budget: u64 = 512 * 1024 * 1024;
     let mut kinds = BTreeMap::new();
     for n in names.iter().filter(|n| part_key(n).ends_with(".rels")) {
         let Some(src_dir) = rels_source_dir(&part_key(n)) else { continue };
-        let Ok(els) = read_zip_part(&mut zip, n).and_then(|xml| xml_elements(&xml)) else { continue };
+        let xml = match read_zip_part_within(&mut zip, n, &mut budget) {
+            Ok(xml) => xml,
+            Err(PartError::OverBudget) => return Err(format!("{n}: relationship check stopped at its decompression limit")),
+            Err(PartError::Unreadable) => continue,
+        };
+        let Ok(els) = xml_elements(&xml) else { continue };
         for (_, attrs) in els.iter().filter(|(el, _)| el == "Relationship") {
             let Some(kind) = attr(attrs, "Type").and_then(|t| t.rsplit('/').next()) else { continue };
             let target = attr(attrs, "Target").unwrap_or("");
@@ -329,3 +368,36 @@ fn holds_something_uncached(zip: &mut Zip<'_>, name: &str, marker: &'static str,
         buf.clear();
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use std::io::Write as _;
+
+    use super::*;
+
+    /// A package with `count` relationship parts of `size` bytes each, none of them describing an
+    /// existing part.
+    fn many_rels(count: usize, size: usize) -> Vec<u8> {
+        let mut z = zip::ZipWriter::new(Cursor::new(Vec::new()));
+        let opts = zip::write::SimpleFileOptions::default().compression_method(zip::CompressionMethod::Deflated);
+        let head = r#"<?xml version="1.0"?><Relationships xmlns="http://schemas.openxmlformats.org/package/2006/relationships"><Relationship Id="rId1" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/custom" Target="https://example.com" TargetMode="External"/>"#;
+        let tail = "</Relationships>";
+        let filler = " ".repeat(size.saturating_sub(head.len() + tail.len()));
+        for i in 0..count {
+            z.start_file(format!("xl/_rels/part{i}.xml.rels"), opts).unwrap();
+            z.write_all(head.as_bytes()).unwrap();
+            z.write_all(filler.as_bytes()).unwrap();
+            z.write_all(tail.as_bytes()).unwrap();
+        }
+        z.finish().unwrap().into_inner()
+    }
+
+    #[test]
+    fn relationship_parts_count_against_the_decompression_budget() {
+        // Each part fits the per-part allowance, but together they need more than the budget.
+        let bytes = many_rels(8, 64 * 1024);
+        assert!(relationship_kinds_within(&bytes, 256 * 1024).is_err());
+        let kinds = relationship_kinds_within(&bytes, 1024 * 1024).unwrap();
+        assert_eq!(kinds.get("custom").map(String::as_str), Some("custom"));
+    }
+}

crates/xlsx/src/richdata.rs

@@ -142,22 +142,13 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
     let Some(image_rel_list) = read_xml(cx, &image_rels_path, "richValueRels")? else { return Ok(vec![]) };
     let image_rels = cx.pkg.rels(&image_rels_path)?;
     let structures = entries(cx, &structures, "s")?;
-    // Each structure's key layout, worked out once: every value would otherwise walk its
-    // structure's keys again. Only local-image structures matter here.
-    let layouts: Vec<Option<Layout>> = structures.iter().map(|s| Layout::of(s)).collect();
     let image_rel_list = entries(cx, &image_rel_list, "rel")?;
-    // Relationships by id, a repeated id recorded as invalid (`None`), so a value's lookup is
-    // one probe rather than a scan of the whole table for duplicates.
-    let mut rels_by_id: HashMap<&str, Option<&Rel>> = HashMap::new();
-    for rel in &image_rels {
-        rels_by_id.entry(rel.id.as_str()).and_modify(|r| *r = None).or_insert(Some(rel));
-    }
     let values = entries(cx, &data, "rv")?;
     let mut pictures = Vec::with_capacity(values.len());
     let mut cache = HashMap::new();
     let mut total = 0usize;
     for value in values {
-        let picture = read_value(cx, value, &layouts, &image_rel_list, &rels_by_id, &mut cache, &mut total)?;
+        let picture = read_value(cx, value, &structures, &image_rel_list, &image_rels, &mut cache, &mut total)?;
         if picture.is_none() {
             cx.warn("some rich values are unsupported or malformed; their scalar fallbacks were retained (cell pictures may be missing)");
         }
@@ -197,56 +188,43 @@ pub fn read(cx: &mut Ctx<'_>, workbook_rels: &[Rel]) -> Result<Vec<Option<Arc<Ce
         .collect())
 }
 
-/// Where a `_localImage` structure keeps the values a picture needs.
-struct Layout {
-    keys: usize,
-    /// Index of the one `_rvRel:LocalImageIdentifier` key of type `i`, if exactly one.
-    image: Option<usize>,
-    /// Index of the one `Text` key of type `s`, if exactly one.
-    text: Option<usize>,
-}
-
-impl Layout {
-    fn of(structure: &El) -> Option<Layout> {
-        if structure.attr("t") != Some("_localImage") {
-            return None;
-        }
-        let keys: Vec<&El> = structure.kids("k").collect();
-        let one = |name: &str, ty: &str| {
-            let mut matches = keys.iter().enumerate().filter(|(_, k)| k.attr("n") == Some(name));
-            let (i, key) = matches.next()?;
-            (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(i)
-        };
-        Some(Layout { keys: keys.len(), image: one("_rvRel:LocalImageIdentifier", "i"), text: one("Text", "s") })
-    }
-}
-
 fn read_value(
     cx: &mut Ctx<'_>,
     value: &El,
-    layouts: &[Option<Layout>],
+    structures: &[&El],
     image_rel_list: &[&El],
-    rels_by_id: &HashMap<&str, Option<&Rel>>,
+    image_rels: &[Rel],
     cache: &mut HashMap<(String, String), Arc<CellPicture>>,
     total: &mut usize,
 ) -> Result<Option<Arc<CellPicture>>, IoError> {
-    let Some(Some(layout)) = value.attr_u32("s").and_then(|n| layouts.get(n as usize)) else { return Ok(None) };
-    let values: Vec<_> = value.kids("v").collect();
-    if layout.keys != values.len() {
+    let Some(structure) = value.attr_u32("s").and_then(|n| structures.get(n as usize)) else { return Ok(None) };
+    if structure.attr("t") != Some("_localImage") {
         return Ok(None);
     }
-    let lookup = |slot: Option<usize>| slot.and_then(|i| values.get(i)).map(|v| v.text.as_str());
-    let Some(rel_id) =
-        lookup(layout.image).and_then(|v| v.trim().parse::<usize>().ok()).and_then(|n| image_rel_list.get(n)).and_then(|rel| rel.attr("id"))
+    let keys: Vec<_> = structure.kids("k").collect();
+    let values: Vec<_> = value.kids("v").collect();
+    if keys.len() != values.len() {
+        return Ok(None);
+    }
+    let lookup = |name: &str, ty: &str| {
+        let mut matches = keys.iter().zip(&values).filter(|(k, _)| k.attr("n") == Some(name));
+        let (key, value) = matches.next()?;
+        (matches.next().is_none() && key.attr("t") == Some(ty)).then_some(value.text.as_str())
+    };
+    let Some(rel_id) = lookup("_rvRel:LocalImageIdentifier", "i")
+        .and_then(|v| v.trim().parse::<usize>().ok())
+        .and_then(|n| image_rel_list.get(n))
+        .and_then(|rel| rel.attr("id"))
     else {
         return Ok(None);
     };
-    let Some(found) = rels_by_id.get(rel_id) else { return Ok(None) };
-    let Some(rel) = found.filter(|rel| rel.kind == "image" && !rel.external) else {
+    let mut matches = image_rels.iter().filter(|rel| rel.id == rel_id);
+    let Some(rel) = matches.next() else { return Ok(None) };
+    if matches.next().is_some() || rel.kind != "image" || rel.external {
         cx.warn("a cell picture has an external or invalid image relationship; kept its scalar fallback");
         return Ok(None);
-    };
-    let alt = lookup(layout.text).unwrap_or("").to_string();
+    }
+    let alt = lookup("Text", "s").unwrap_or("").to_string();
     let key = (normalize(&rel.target), alt.clone());
     if let Some(picture) = cache.get(&key) {
         return Ok(Some(picture.clone()));

crates/xlsx/src/tests/richdata_tests.rs

@@ -294,27 +294,3 @@ fn picture_metadata_limits_and_relationship_read_errors_do_not_block_workbooks()
         assert!(report.warnings.iter().any(|w| w.contains("cell-picture data could not be read")), "{:?}", report.warnings);
     }
 }
-
-/// Many values over one wide structure, and a repeated relationship id: the structure's layout
-/// is worked out once and relationships are indexed, so the import is linear in the records;
-/// the repeated id is invalid and keeps the scalar fallback.
-#[test]
-fn wide_structures_and_repeated_relationship_ids_are_resolved_through_indexes() {
-    let mut parts = independent_parts(false);
-    // 200,000 keys in one structure and 50,000 short values that name it: rebuilding the key
-    // list per value would be ten billion steps.
-    let padding = r#"<k n="pad" t="s"/>"#.repeat(200_000);
-    replace(&mut parts, "rich/structures.xml", r#"<k n="CalcOrigin" t="i"/>"#, &format!(r#"<k n="CalcOrigin" t="i"/>{padding}"#));
-    let values = r#"<rv s="1"><v/></rv>"#.repeat(50_000);
-    replace(&mut parts, "rich/values.xml", r#"<rv s="1"><v>green &amp; &lt;image&gt;</v><v>1</v><v>5</v></rv>"#, &values);
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("picture")), "{:?}", report.warnings);
-    // The same id twice makes every reference to it invalid.
-    let mut parts = independent_parts(false);
-    let dup = r#"<Relationship Id="opaqueImageId" Type="http://schemas.openxmlformats.org/officeDocument/2006/relationships/image" Target="../media/original.bin"/>"#;
-    replace(&mut parts, "rich/_rels/images.xml.rels", dup, &dup.repeat(2));
-    let (wb, report) = read_xlsx(&zip(&parts)).unwrap();
-    assert!(!wb.sheet(0).unwrap().cell_pictures.contains_key(&at("A1")));
-    assert!(report.warnings.iter().any(|w| w.contains("invalid image relationship")), "{:?}", report.warnings);
-}