← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

git clone https://code.inqk.net/crossmate.git


commit 27b2a410ead5da69415c847eb0d362bc9aa08c4e
parent 47424d7da9685b5e4b53cd8046ec8470764f277d
Author: Michael Camilleri <[email protected]>
Date:   Wed,  1 Jul 2026 18:53:51 +0900

Harden .xd parse boundaries against untrusted sources

Two related fixes for the crossword parser, which runs on attacker-
influenced input (a synced Game asset, an invite payload, an imported
file) and, on invite accept, synchronously on the main actor:

- XD.segment walked the full composition tree for an answer that admits
  no valid segmentation over many free cells - a sub-1KB crafted
  puzzleSource could drive minutes-to-hours of work and freeze the UI on
  tap-Accept.  Rewrite the recursion as a memoized word-break DP keyed
  on (cellIndex, answerIndex), collapsing it to O(word x answer), and
  cap each subproblem at maxResults.

- add size/length caps at the parse boundaries so no single input can
  blow up parse cost or memory. XD.parse rejects sources over
  maxSourceBytes (262 KB, ~80x the largest bundled puzzle) and clue text
  over maxClueTextLength; ImportService checks on-disk file size before
  reading; RecordSerializer checks the puzzleSource CKAsset size before
  pulling it into memory.

Co-Authored-By: Claude Opus 4.8 <[email protected]>

Diffstat

MCrossmate/Models/XD.swift | 93++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------
MCrossmate/Services/ImportService.swift | 10++++++++++
MCrossmate/Sync/RecordSerializer.swift | 13+++++++++++++
MTests/Unit/XDAcceptTests.swift | 103+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

4 files changed, 199 insertions(+), 20 deletions(-)

diff --git a/Crossmate/Models/XD.swift b/Crossmate/Models/XD.swift

@@ -6,6 +6,20 @@ import Foundation
 struct XD: Sendable {
     static let currentCmVersion = 7
 
+    /// Upper bound on a `.xd` source handed to `parse`. The largest puzzle we
+    /// ship is ~3 KB, so this is ~80× real content — no genuine puzzle is ever
+    /// rejected, but it caps parse cost and memory on an untrusted source (a
+    /// synced Game asset, an invite payload, an imported file). Does not replace
+    /// the algorithmic fix in `segment`; it bounds the general boundary cost.
+    static let maxSourceBytes = 262_144
+
+    /// Upper bound on a single clue's text. The longest real clue is under 100
+    /// characters. The overall source cap alone doesn't tame per-clue cost:
+    /// `XDMarkup.segments` rescans to end-of-string for every unclosed markup
+    /// span (O(n²) in one clue) and `parseCrossReferences` runs a backtracking
+    /// regex, so a single oversized clue under the source cap is still costly.
+    static let maxClueTextLength = 1_024
+
     let title: String?
     let publisher: String?
     let author: String?
@@ -85,6 +99,7 @@ struct XD: Sendable {
         case missingGrid
         case missingClues
         case raggedGrid
+        case sourceTooLarge
         case malformedClue(String)
         case unknownGridCharacter(Character)
         case clueAnswerMismatch(String)
@@ -99,6 +114,8 @@ struct XD: Sendable {
                 return ".xd source has no clues section"
             case .raggedGrid:
                 return ".xd grid rows have inconsistent widths"
+            case .sourceTooLarge:
+                return ".xd source exceeds the maximum allowed size"
             case .malformedClue(let line):
                 return "malformed .xd clue: \(line)"
             case .unknownGridCharacter(let ch):
@@ -125,6 +142,8 @@ struct XD: Sendable {
                 return "is missing its clues"
             case .raggedGrid:
                 return "has a grid Crossmate couldn't read"
+            case .sourceTooLarge:
+                return "is too large for Crossmate to open"
             case .malformedClue:
                 return "has a clue Crossmate couldn't read"
             case .unknownGridCharacter:
@@ -140,6 +159,9 @@ struct XD: Sendable {
     }
 
     static func parse(_ source: String) throws -> XD {
+        guard source.utf8.count <= maxSourceBytes else {
+            throw ParseError.sourceTooLarge
+        }
         let sections = splitIntoSections(source)
         guard sections.count >= 2 else { throw ParseError.missingGrid }
         guard sections.count >= 3 else { throw ParseError.missingClues }
@@ -553,6 +575,10 @@ struct XD: Sendable {
                     .trimmingCharacters(in: .whitespaces)
             }
 
+            guard afterDot.count <= maxClueTextLength else {
+                throw ParseError.malformedClue(line)
+            }
+
             if clueTexts[key] == nil {
                 clueOrder.append(key)
             }
@@ -709,42 +735,69 @@ struct XD: Sendable {
         maxResults: Int
     ) -> [[String]] {
         let chars = Array(answer)
-        var results: [[String]] = []
 
-        func recurse(cellIndex: Int, answerIndex: Int, current: [String]) {
-            guard results.count < maxResults else { return }
+        // The set of valid segmentations of the answer suffix from a given
+        // `(cellIndex, answerIndex)` state is independent of how that state was
+        // reached, so we memoize it. Without this, a crafted answer that admits
+        // no valid segmentation over many free cells walks the entire
+        // C(answer-1, cells-1) composition tree — a sub-1KB puzzle can drive
+        // minutes-to-hours of work on the main actor during invite accept.
+        // Memoizing collapses that to an O(word × answer) word-break DP.
+        var memo: [Int: [[String]]] = [:]
+
+        func solve(cellIndex: Int, answerIndex: Int) -> [[String]] {
             if cellIndex == word.count {
-                if answerIndex == chars.count {
-                    results.append(current)
-                }
-                return
+                return answerIndex == chars.count ? [[]] : []
             }
-            guard answerIndex < chars.count else { return }
+            guard answerIndex < chars.count else { return [] }
+
+            let key = cellIndex * (chars.count + 1) + answerIndex
+            if let cached = memo[key] { return cached }
 
             let position = word[cellIndex]
-            guard case .open(let solution, _, _) = cells[position.row][position.col] else { return }
+            guard case .open(let solution, _, _) = cells[position.row][position.col] else {
+                memo[key] = []
+                return []
+            }
             let remainingCells = word.count - cellIndex - 1
 
+            var results: [[String]] = []
+            // Prepend `segment` to every valid completion of the remaining
+            // cells, capped at `maxResults`. Each subproblem is itself capped at
+            // `maxResults`, which is sufficient because the caller never needs
+            // more than that many total.
+            func extend(length: Int) {
+                let endIndex = answerIndex + length
+                guard endIndex <= chars.count else { return }
+                let segment = String(chars[answerIndex..<endIndex])
+                for suffix in solve(cellIndex: cellIndex + 1, answerIndex: endIndex) {
+                    results.append([segment] + suffix)
+                    if results.count >= maxResults { break }
+                }
+            }
+
             if let solution {
                 let solutionLength = Array(solution).count
                 let endIndex = answerIndex + solutionLength
-                guard endIndex <= chars.count else { return }
-                let segment = String(chars[answerIndex..<endIndex])
-                guard normalizedAnswer(segment) == normalizedAnswer(solution) else { return }
-                recurse(cellIndex: cellIndex + 1, answerIndex: endIndex, current: current + [segment])
+                if endIndex <= chars.count,
+                   normalizedAnswer(String(chars[answerIndex..<endIndex])) == normalizedAnswer(solution) {
+                    extend(length: solutionLength)
+                }
             } else {
                 let maxLength = chars.count - answerIndex - remainingCells
-                guard maxLength >= 1 else { return }
-                for length in 1...maxLength {
-                    let endIndex = answerIndex + length
-                    let segment = String(chars[answerIndex..<endIndex])
-                    recurse(cellIndex: cellIndex + 1, answerIndex: endIndex, current: current + [segment])
+                if maxLength >= 1 {
+                    for length in 1...maxLength {
+                        extend(length: length)
+                        if results.count >= maxResults { break }
+                    }
                 }
             }
+
+            memo[key] = results
+            return results
         }
 
-        recurse(cellIndex: 0, answerIndex: 0, current: [])
-        return results
+        return solve(cellIndex: 0, answerIndex: 0)
     }
 
     private struct Position: Hashable {

diff --git a/Crossmate/Services/ImportService.swift b/Crossmate/Services/ImportService.swift

@@ -20,6 +20,16 @@ final class ImportService {
             }
         }
 
+        // Reject an oversized file before pulling it into memory or handing it
+        // to the parser/converter. The parser enforces the same bound on the
+        // resulting `.xd`, but checking on-disk size first avoids reading a
+        // large blob at all. A missing size reading falls through to the read,
+        // which the parser still bounds.
+        if let size = try? url.resourceValues(forKeys: [.fileSizeKey]).fileSize,
+           size > XD.maxSourceBytes {
+            return nil
+        }
+
         let source: String
         do {
             switch url.pathExtension.lowercased() {

diff --git a/Crossmate/Sync/RecordSerializer.swift b/Crossmate/Sync/RecordSerializer.swift

@@ -870,6 +870,19 @@ enum RecordSerializer {
         if let asset = record["puzzleSource"] as? CKAsset,
            let fileURL = asset.fileURL {
             do {
+                // A co-player writes this asset into the shared zone, so treat
+                // its size as untrusted: reject an oversized blob before reading
+                // it into memory. The parser enforces the same bound, but the
+                // asset is an external file that could dwarf the ~1 MB record
+                // limit, so gate on the on-disk size first.
+                if let size = try? fileURL.resourceValues(forKeys: [.fileSizeKey]).fileSize,
+                   size > XD.maxSourceBytes {
+                    print(
+                        "RecordSerializer: puzzleSource asset for \(recordName) " +
+                        "exceeds \(XD.maxSourceBytes) bytes (\(size)) — skipping"
+                    )
+                    return entity
+                }
                 let source = try String(contentsOf: fileURL, encoding: .utf8)
                 entity.puzzleSource = source
                 if let xd = try? XD.parse(source) {

diff --git a/Tests/Unit/XDAcceptTests.swift b/Tests/Unit/XDAcceptTests.swift

@@ -356,6 +356,109 @@ struct XDAcceptTests {
         }
     }
 
+    @Test("Free cells receive a unique answer segmentation")
+    func freeCellsReceiveUniqueSegmentation() throws {
+        // A '.' cell has no known solution, so the clue answer must be
+        // distributed across it. "XYB" over `.B` has exactly one valid split:
+        // the free cell takes "XY" and the fixed 'B' cell matches "B".
+        let puzzle = Puzzle(xd: try XD.parse("""
+        Title: Segmentation
+        CmVer: 3
+
+
+        .B
+
+
+        A1. Two cells ~ XYB
+        """))
+
+        #expect(puzzle.cells[0][0].solution == "XY")
+        #expect(puzzle.cells[0][1].solution == "B")
+    }
+
+    @Test("Unsegmentable answer over many free cells fails fast")
+    func unsegmentableAnswerOverManyFreeCellsFailsFast() throws {
+        // 30 free cells followed by a fixed 'Z', with a 61-char answer that
+        // does not end in Z. No valid segmentation exists, so the naive
+        // recursion would explore every one of C(59, 29) ≈ 10^16 compositions
+        // before failing — effectively forever. The memoized word-break DP
+        // collapses this to O(cells × answer), so parsing returns promptly with
+        // a mismatch. If this test hangs, the memoization has regressed.
+        let grid = String(repeating: ".", count: 30) + "Z"
+        let answer = String(repeating: "A", count: 61)
+        let source = """
+        Title: DoS
+        CmVer: 3
+
+
+        \(grid)
+
+
+        A1. Crafted ~ \(answer)
+        """
+
+        #expect(throws: XD.ParseError.self) {
+            try XD.parse(source)
+        }
+    }
+
+    @Test("Oversized source is rejected before parsing")
+    func oversizedSourceIsRejected() throws {
+        let source = String(repeating: "A", count: XD.maxSourceBytes + 1)
+
+        do {
+            _ = try XD.parse(source)
+            Issue.record("expected parse to throw sourceTooLarge")
+        } catch let error as XD.ParseError {
+            guard case .sourceTooLarge = error else {
+                Issue.record("expected sourceTooLarge, got \(error)")
+                return
+            }
+        }
+    }
+
+    @Test("A source at the size limit still parses")
+    func sourceAtLimitParses() throws {
+        // A well-formed minimal puzzle padded with comment-free filler in the
+        // metadata section up to exactly the cap must still parse — the bound is
+        // inclusive and far above any real puzzle.
+        let base = """
+        Title: Padded
+
+
+        A
+
+
+        A1. Letter ~ A
+        D1. Letter ~ A
+        """
+        let padding = String(repeating: " ", count: XD.maxSourceBytes - base.utf8.count)
+        let source = base + padding
+
+        #expect(source.utf8.count == XD.maxSourceBytes)
+        #expect(throws: Never.self) {
+            try XD.parse(source)
+        }
+    }
+
+    @Test("Over-long clue text is rejected")
+    func overLongClueTextIsRejected() throws {
+        let longText = String(repeating: "x", count: XD.maxClueTextLength + 1)
+        let source = """
+        Title: Long Clue
+
+
+        AB
+
+
+        A1. \(longText) ~ AB
+        """
+
+        #expect(throws: XD.ParseError.self) {
+            try XD.parse(source)
+        }
+    }
+
     @Test("Check accepts alternate entries")
     func checkAcceptsAlternateEntries() throws {
         let source = """