Implement String Deduplication with Metadata Preservation

[unclesp1d3r]

Problem Statement

Currently, the string extraction pipeline generates multiple FoundString entries for identical string text that appears in different locations within a binary. This creates significant noise in the output and makes analysis difficult.

Example scenario:

• The string "https://example.com" appears in:
  • .rodata section at offset 0x1000
  • .data section at offset 0x3500
  • PE resource section at offset 0x8000

Without deduplication, three separate FoundString entries are emitted, even though they represent the same semantic content.

Goals

Implement intelligent string deduplication that:

1. Reduces noise by consolidating duplicate string text into canonical entries
2. Preserves metadata from all occurrences (offsets, sections, sources)
3. Merges tags intelligently to combine semantic classifications
4. Calculates combined relevance scores based on occurrence patterns
5. Maintains traceability so analysts can see all locations where a string appears

Proposed Solution

Implementation Plan

Create src/extraction/dedup.rs with the following components:

1. Canonical String Structure

pub struct CanonicalString {
    pub text: String,
    pub encoding: Encoding,
    pub occurrences: Vec<StringOccurrence>,
    pub merged_tags: Vec<Tag>,
    pub combined_score: i32,
}

pub struct StringOccurrence {
    pub offset: u64,
    pub rva: Option<u64>,
    pub section: Option<String>,
    pub source: StringSource,
    pub original_tags: Vec<Tag>,
    pub original_score: i32,
}

2. Deduplication Algorithm

pub fn deduplicate(strings: Vec<FoundString>) -> Vec<CanonicalString> {
    // 1. Group strings by (text, encoding) key
    // 2. For each group, create CanonicalString with:
    //    - All occurrences preserved
    //    - Union of all tags across occurrences
    //    - Combined score = max(scores) + occurrence_bonus
    // 3. Sort by combined_score descending
}

3. Scoring Strategy

• Base score: Take the maximum score from all occurrences
• Occurrence bonus: +5 points for each additional occurrence (indicates importance)
• Cross-section bonus: +10 if string appears in multiple section types
• Multi-source bonus: +15 if string appears from different sources (e.g., both section data and imports)

4. Integration Points

Update the extraction pipeline in the architecture:

String Extraction → **Deduplication** → Classification → Ranking → Output

Output Format Considerations

The deduplicated output should show:

• Primary metadata from the "best" occurrence (highest original score)
• Count of total occurrences
• Optional verbose mode to list all locations

JSONL format:

{
  "text": "https://example.com",
  "encoding": "Utf8",
  "occurrences": 3,
  "locations": [
    {"offset": 4096, "section": ".rodata", "source": "SectionData"},
    {"offset": 13568, "section": ".data", "source": "SectionData"},
    {"offset": 32768, "section": ".rsrc", "source": "ResourceString"}
  ],
  "tags": ["Url"],
  "score": 95
}

Acceptance Criteria

• src/extraction/dedup.rs module created with deduplication logic
• deduplicate() function handles identical text with different encodings separately
• All occurrence metadata is preserved in the canonical structure
• Tags are merged intelligently (union, with duplicates removed)
• Combined scoring algorithm implemented with occurrence bonuses
• Unit tests covering:
  • Basic deduplication of identical strings
  • Metadata preservation from multiple occurrences
  • Tag merging logic
  • Score calculation with bonuses
  • Edge cases (empty strings, single occurrence, etc.)
• Integration test with real binary containing duplicate strings
• Documentation updated in docs/src/architecture.md

Technical Considerations

Edge Cases

• Empty strings: Should they be deduplicated or filtered?
• Whitespace variations: Are " test" and "test " the same?
• Encoding normalization: How to handle UTF-8 vs UTF-16 of same text?

Performance

• Use HashMap<(String, Encoding), Vec<FoundString>> for efficient grouping
• Consider memory implications for binaries with thousands of duplicate strings
• Benchmark against large binaries (>100MB) to ensure acceptable performance

Configuration

Consider adding configuration options:

• --no-dedup: Skip deduplication for raw output
• --dedup-threshold: Only deduplicate strings appearing N+ times
• --dedup-mode: [strict|normalized] for handling whitespace

Related Files

• src/types.rs: Contains FoundString structure definition
• src/extraction/mod.rs: Main extraction module (currently placeholder)
• docs/src/architecture.md: Architecture documentation to update

Task Context

Requirements: 2.5
Task-ID: stringy-analyzer/string-deduplication

[unclesp1d3r]

@coderabbitai Enhance this issue body with additional context and a proposed solution. Improve the issue title and assign the proper labels and other metadata.

[coderabbitai]

Tip

For best results, initiate chat on the files or code changes.

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
# Fetch the details of issue #13
gh issue view 13 --json title,body,labels,assignees,author,state,createdAt

Length of output: 1270

---

🏁 Script executed:

#!/bin/bash
# Find the extraction module structure to understand the codebase
fd -t f . src/extraction 2>/dev/null || echo "No src/extraction directory found"

# Look for any existing string-related extraction code
fd -e rs -t f | xargs grep -l "string" | head -20

# Check the project structure
ls -la src/ 2>/dev/null || echo "No src directory"

# Look for any documentation about the analyzer
fd -e md -t f | head -10

Length of output: 846

---

🏁 Script executed:

#!/bin/bash
# Read the extraction module to understand current implementation
echo "=== src/extraction/mod.rs ==="
cat src/extraction/mod.rs

echo -e "\n=== src/types.rs (relevant parts) ==="
cat src/types.rs

echo -e "\n=== Architecture docs ==="
cat docs/src/architecture.md 2>/dev/null || echo "No architecture doc"

echo -e "\n=== Check for existing string extraction ==="
rg -n "struct.*String|fn.*extract.*string" --type rust -i

Length of output: 10488

---

🏁 Script executed:

#!/bin/bash
# Update the issue with enhanced content

gh issue edit 13 \
  --title "Implement String Deduplication with Metadata Preservation" \
  --body "## Problem Statement

Currently, the string extraction pipeline generates multiple \`FoundString\` entries for identical string text that appears in different locations within a binary. This creates significant noise in the output and makes analysis difficult.

**Example scenario:**
- The string \"https://example.com\" appears in:
  - \`.rodata\` section at offset 0x1000
  - \`.data\` section at offset 0x3500
  - PE resource section at offset 0x8000

Without deduplication, three separate \`FoundString\` entries are emitted, even though they represent the same semantic content.

## Goals

Implement intelligent string deduplication that:
1. **Reduces noise** by consolidating duplicate string text into canonical entries
2. **Preserves metadata** from all occurrences (offsets, sections, sources)
3. **Merges tags intelligently** to combine semantic classifications
4. **Calculates combined relevance scores** based on occurrence patterns
5. **Maintains traceability** so analysts can see all locations where a string appears

## Proposed Solution

### Implementation Plan

Create \`src/extraction/dedup.rs\` with the following components:

#### 1. Canonical String Structure
\`\`\`rust
pub struct CanonicalString {
    pub text: String,
    pub encoding: Encoding,
    pub occurrences: Vec<StringOccurrence>,
    pub merged_tags: Vec<Tag>,
    pub combined_score: i32,
}

pub struct StringOccurrence {
    pub offset: u64,
    pub rva: Option<u64>,
    pub section: Option<String>,
    pub source: StringSource,
    pub original_tags: Vec<Tag>,
    pub original_score: i32,
}
\`\`\`

#### 2. Deduplication Algorithm

\`\`\`rust
pub fn deduplicate(strings: Vec<FoundString>) -> Vec<CanonicalString> {
    // 1. Group strings by (text, encoding) key
    // 2. For each group, create CanonicalString with:
    //    - All occurrences preserved
    //    - Union of all tags across occurrences
    //    - Combined score = max(scores) + occurrence_bonus
    // 3. Sort by combined_score descending
}
\`\`\`

#### 3. Scoring Strategy

- **Base score**: Take the maximum score from all occurrences
- **Occurrence bonus**: +5 points for each additional occurrence (indicates importance)
- **Cross-section bonus**: +10 if string appears in multiple section types
- **Multi-source bonus**: +15 if string appears from different sources (e.g., both section data and imports)

#### 4. Integration Points

Update the extraction pipeline in the architecture:
\`\`\`
String Extraction → **Deduplication** → Classification → Ranking → Output
\`\`\`

### Output Format Considerations

The deduplicated output should show:
- Primary metadata from the \"best\" occurrence (highest original score)
- Count of total occurrences
- Optional verbose mode to list all locations

**JSONL format:**
\`\`\`json
{
  \"text\": \"https://example.com\",
  \"encoding\": \"Utf8\",
  \"occurrences\": 3,
  \"locations\": [
    {\"offset\": 4096, \"section\": \".rodata\", \"source\": \"SectionData\"},
    {\"offset\": 13568, \"section\": \".data\", \"source\": \"SectionData\"},
    {\"offset\": 32768, \"section\": \".rsrc\", \"source\": \"ResourceString\"}
  ],
  \"tags\": [\"Url\"],
  \"score\": 95
}
\`\`\`

## Acceptance Criteria

- [ ] \`src/extraction/dedup.rs\` module created with deduplication logic
- [ ] \`deduplicate()\` function handles identical text with different encodings separately
- [ ] All occurrence metadata is preserved in the canonical structure
- [ ] Tags are merged intelligently (union, with duplicates removed)
- [ ] Combined scoring algorithm implemented with occurrence bonuses
- [ ] Unit tests covering:
  - [ ] Basic deduplication of identical strings
  - [ ] Metadata preservation from multiple occurrences
  - [ ] Tag merging logic
  - [ ] Score calculation with bonuses
  - [ ] Edge cases (empty strings, single occurrence, etc.)
- [ ] Integration test with real binary containing duplicate strings
- [ ] Documentation updated in \`docs/src/architecture.md\`

## Technical Considerations

### Edge Cases
- **Empty strings**: Should they be deduplicated or filtered?
- **Whitespace variations**: Are \" test\" and \"test \" the same?
- **Encoding normalization**: How to handle UTF-8 vs UTF-16 of same text?

### Performance
- Use \`HashMap<(String, Encoding), Vec<FoundString>>\` for efficient grouping
- Consider memory implications for binaries with thousands of duplicate strings
- Benchmark against large binaries (>100MB) to ensure acceptable performance

### Configuration
Consider adding configuration options:
- \`--no-dedup\`: Skip deduplication for raw output
- \`--dedup-threshold\`: Only deduplicate strings appearing N+ times
- \`--dedup-mode\`: [strict|normalized] for handling whitespace

## Related Files

- \`src/types.rs\`: Contains \`FoundString\` structure definition
- \`src/extraction/mod.rs\`: Main extraction module (currently placeholder)
- \`docs/src/architecture.md\`: Architecture documentation to update

## Task Context

**Requirements:** 2.5  
**Task-ID:** stringy-analyzer/string-deduplication"

echo "Issue #13 has been updated successfully!"

Length of output: 103

---

@unclesp1d3r I've successfully enhanced issue #13! Here's what I updated:

Changes Made

📝 Improved Title

• Before: "String Deduplication"
• After: "Implement String Deduplication with Metadata Preservation"

📄 Enhanced Issue Body

The issue now includes:

1. Problem Statement - Clear explanation with concrete examples of why deduplication is needed
2. Goals - Five specific objectives for the implementation
3. Proposed Solution with:
   • Detailed implementation plan for src/extraction/dedup.rs
   • Rust code structure for CanonicalString and StringOccurrence
   • Intelligent scoring strategy (base score + occurrence bonuses + cross-section/multi-source bonuses)
   • Integration points in the extraction pipeline
   • Output format examples (JSONL)
4. Acceptance Criteria - Comprehensive checklist with 7 main items and 5 unit test scenarios
5. Technical Considerations - Edge cases, performance considerations, and configuration options
6. Related Files - Links to relevant source files for implementation

🏷️ Labels & Metadata

The existing labels are already appropriate and well-assigned:

• ✅ area:analyzer - Correct functional area
• ✅ type:enhancement - Appropriate for new feature
• ✅ status:backlog - Current status
• ✅ lang:rust - Implementation language
• ✅ needs:tests - Aligns with acceptance criteria
• ✅ Assigned to you (unclesp1d3r)

The issue is now ready for implementation with clear technical guidance, acceptance criteria, and considerations for edge cases and performance! 🚀

[unclesp1d3r]

@coderabbitai Should this be broken up into any sub-issues or is this a small enough unit of work?

[coderabbitai]

Tip

For best results, initiate chat on the files or code changes.

🧩 Analysis chain

🏁 Script executed:

#!/bin/bash
# Check the size and complexity of other issues in the project to understand typical granularity
gh issue list --limit 50 --json number,title,labels,body --state all | jq -r '.[] | "\(.number): \(.title) | Labels: \(.labels | map(.name) | join(", ")) | Body length: \((.body // "") | length)"' | head -20

Length of output: 3523

---

@unclesp1d3r Based on the project's typical issue granularity, this should remain a single issue. Here's my analysis:

✅ Keep as Single Issue

After reviewing similar issues in your project, #13 fits perfectly within your typical scope:

Similar-sized issues:

• Implement Main String Extraction Orchestrator and Pipeline Integration #36: Main String Extraction Orchestrator (~4,948 chars)
• Complete End-to-End Pipeline Integration with Error Recovery and Testing #37: End-to-End Pipeline Integration (~5,909 chars)
• Integrate Import/Export Symbol Extraction into String Analysis Pipeline #59: Import/Export Symbol Integration (~4,807 chars)
• Performance: Implement Regex Compilation Caching for Semantic Classifier #33: Regex Compilation Caching (~4,754 chars)

Why keep it unified:

1. Cohesive Feature - All components serve one purpose: intelligent deduplication
2. Tight Coupling - CanonicalString, StringOccurrence, scoring algorithm, and tests are interdependent
3. Manageable Scope - At 2.5 story points, this is appropriately sized for a single sprint/iteration
4. Clear Boundaries - Single module (src/extraction/dedup.rs) with well-defined inputs/outputs
5. Atomic Value - Only delivers value when complete; partial implementation doesn't provide benefits

🔧 Optional Split (if needed later)

If you encounter blockers or want smaller increments, you could split into:

1. Phase 1: Core deduplication logic + basic tests (data structures + grouping algorithm)
2. Phase 2: Advanced scoring + integration tests (cross-section bonuses, multi-source detection)

However, I'd recommend implementing this as-is. The acceptance criteria provides good checkpoints for tracking progress without creating separate issues.