SECURITY: data-structure-typed Security Guide

Version: 2.0.4
Last Updated: January 2026
Status: ✅ Actively Maintained

Security Overview

data-structure-typed is a data structure library focused on performance and usability. Security considerations are primarily around resource exhaustion, type safety, and safe iteration.

Scope

This library is NOT designed to:

❌ Encrypt or hash data
❌ Validate untrusted input
❌ Prevent timing attacks
❌ Protect against side-channel attacks
❌ Sanitize user input

This library DOES protect against:

✅ Buffer overflows (impossible in JavaScript)
✅ Type confusion attacks (TypeScript prevents at compile time)
✅ Null/undefined dereferences (defensive checks)
✅ Uncontrolled memory growth (clear APIs)
✅ Unsafe iteration patterns (documented behavior)

Design Philosophy

Library follows fail-fast principle:

Loud: Errors that indicate bugs throw exceptions
Silent: Missing keys return undefined (standard behavior)
Safe: Type system prevents category errors at compile time

Threat Model

Attack Vectors (In Scope)

1. Unintended Memory Growth

Risk: Attacker adds millions of items, causing OOM

const tree = new RedBlackTree();
for (let i = 0; i < 1000000000; i++) {
  tree.set(i, 'data');  // Unbounded growth
}
// Process runs out of memory

Mitigation:

Monitor structure.size property
Implement size limits in application logic
Clear structures when done: structure.clear()

// ✅ Safe pattern
const tree = new RedBlackTree();
const MAX_SIZE = 100000;

function addSafe(key, value) {
  if (tree.size >= MAX_SIZE) {
    throw new Error('Structure at capacity');
  }
  tree.set(key, value);
}

2. Comparator Exceptions

Risk: Malicious comparator throws or crashes

const tree = new RedBlackTree<number>(
  (a, b) => {
    if (a === null) throw new Error('Hacked!');
    return a - b;
  }
);

tree.set(null, 'value');  // Throws unhandled exception

Mitigation:

Always wrap comparators in try-catch if untrusted
Use pure functions (no side effects)
Validate inputs before tree operations

// ✅ Safe pattern
function safeComparator(a, b) {
  try {
    if (!isNumber(a) || !isNumber(b)) {
      throw new TypeError('Expected numbers');
    }
    return a - b;
  } catch (error) {
    logger.error('Comparator failed:', error);
    throw error;  // Explicit error handling
  }
}

const tree = new RedBlackTree<number>(safeComparator);

3. Iterator Mutation

Risk: Mutating structure during iteration causes inconsistent state

const tree = new RedBlackTree([1, 2, 3]);

for (const item of tree) {
  tree.delete(item);  // Modifying while iterating
  // Behavior is undefined
}

Mitigation:

Don't mutate during iteration
Collect mutations and apply after
Use snapshot iteration if needed

// ✅ Safe pattern
const tree = new RedBlackTree([1, 2, 3]);

// Method 1: Collect mutations
const toDelete = [];
for (const item of tree) {
  if (shouldDelete(item)) toDelete.push(item);
}
toDelete.forEach(item => tree.delete(item));

// Method 2: Snapshot iteration
const items = [...tree];  // Create snapshot
items.forEach(item => tree.delete(item));

4. Type Confusion

Risk: Passing wrong types bypasses type system at runtime

const tree = new RedBlackTree<number>();

// At runtime, TypeScript types are erased
tree.set('not-a-number' as any, 'value');
// Type system didn't prevent this

Mitigation:

Use strict TypeScript settings: strict: true
Avoid as any assertions in untrusted code
Validate types at runtime boundaries

// ✅ Safe pattern
interface ValidInput {
  id: number;
  name: string;
}

function addFromUntrustedSource(input: unknown) {
  if (!isValidInput(input)) {
    throw new TypeError('Invalid input');
  }
  
  const tree = new RedBlackTree<number, ValidInput>();
  tree.set(input.id, input);  // Now type-safe
}

function isValidInput(input: unknown): input is ValidInput {
  return (
    typeof input === 'object' &&
    input !== null &&
    typeof (input as any).id === 'number' &&
    typeof (input as any).name === 'string'
  );
}

5. Infinite Loops

Risk: Comparator causes infinite loop during tree operations

const tree = new RedBlackTree<number>(
  (a, b) => {
    // Intentionally broken comparator
    return 0;  // Always equal
  }
);

tree.addMany([1, 2, 3, 4, 5]);
// May cause infinite loops or stack overflow

Mitigation:

Use strict comparators: consistent and deterministic
Test comparators with large datasets
Set timeout limits for tree operations

// ✅ Safe pattern
function strictComparator<T>(a: T, b: T): number {
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;  // Only returns -1, 0, or 1
}

const tree = new RedBlackTree<number>(strictComparator);

// With timeout wrapper (application level)
function withTimeout<T>(fn: () => T, ms: number): T {
  const controller = new AbortController();
  const timeout = setTimeout(() => controller.abort(), ms);
  
  try {
    return fn();
  } finally {
    clearTimeout(timeout);
  }
}

withTimeout(() => tree.addMany(items), 1000);

Security Guarantees

What This Library Guarantees

Guarantee	Status	Details
No arbitrary code execution	✅ 100%	Only runs provided comparators
No data leaks	✅ 100%	No external communication
No uncontrolled memory growth	⚠️ Partial	Application must set size limits
Type safety	✅ 100%	TypeScript prevents type confusion
Iterator safety	✅ 100%	Clear documented behavior
Protection from invalid input	⚠️ Partial	Application validates input

What This Library Does NOT Guarantee

Guarantee	Status	Details
Constant-time operations	❌ No	Timing attacks possible (crypto use only)
Protection from DoS	⚠️ No	Application must rate-limit
Untrusted input handling	❌ No	Input validation is application's responsibility
Secure random numbers	❌ No	Not applicable (no randomness)
Cryptographic security	❌ No	Not a crypto library

Input Validation

Comparators Must Be Pure

Unsafe: Side effects or external state

// ❌ DO NOT DO THIS
let callCount = 0;
const tree = new RedBlackTree<number>((a, b) => {
  callCount++;  // Side effect!
  return a - b;
});

// ❌ DO NOT DO THIS
const config = getConfig();
const tree = new RedBlackTree<number>((a, b) => {
  const weight = config.weight;  // Mutable external state
  return (a - b) * weight;
});

// ✅ DO THIS
const tree = new RedBlackTree<number>((a, b) => {
  return a - b;  // Pure function
});

const weightedTree = new RedBlackTree<number>((a, b) => {
  return (a - b) * FIXED_WEIGHT;  // Fixed constant
});

Validate Comparators Upfront

// ✅ Validate comparator before using
function validateComparator<T>(comp: (a: T, b: T) => number, samples: T[]): boolean {
  for (let i = 0; i < samples.length; i++) {
    for (let j = i + 1; j < samples.length; j++) {
      const result = comp(samples[i], samples[j]);
      
      // Comparator must return -1, 0, or 1 (or at least consistent)
      if (Math.abs(result) > 1 && result !== 0) {
        return false;  // Invalid comparator
      }
      
      // Transitivity check
      for (let k = j + 1; k < samples.length; k++) {
        const ij = comp(samples[i], samples[j]);
        const jk = comp(samples[j], samples[k]);
        const ik = comp(samples[i], samples[k]);
        
        if (!isTransitive(ij, jk, ik)) {
          return false;  // Comparator violates transitivity
        }
      }
    }
  }
  return true;
}

// Use validated comparator
const myComparator = (a: number, b: number) => a - b;
if (!validateComparator(myComparator, [1, 2, 3])) {
  throw new Error('Invalid comparator');
}

const tree = new RedBlackTree<number>(myComparator);

Bound Structure Size

// ✅ Enforce maximum size
class BoundedTree<K, V> extends RedBlackTree<K, V> {
  private maxSize: number;

  constructor(maxSize: number = 100000) {
    super();
    this.maxSize = maxSize;
  }

  set(key: K, value: V): this {
    if (this.size >= this.maxSize && !this.has(key)) {
      throw new Error(`Tree exceeds max size of ${this.maxSize}`);
    }
    return super.set(key, value);
  }
}

// Use with confidence
const tree = new BoundedTree(10000);

Comparator Safety

Comparator Requirements

A valid comparator must:

Return consistent values

const comp = (a, b) => {
  // ✅ Always returns same value for same inputs
  return a - b;
};

Respect transitivity

// If a < b and b < c, then a < c
const a = 1, b = 2, c = 3;
comp(a, b) < 0    // true
comp(b, c) < 0    // true
comp(a, c) < 0    // must be true

Handle all input types

const comp = (a, b) => {
  // Handle null, undefined, NaN
  if (a == null || b == null) return 0;
  if (isNaN(a) || isNaN(b)) return 0;
  return a - b;
};

Dangerous Comparators

// ❌ DO NOT: Random comparators
const random = (a, b) => Math.random() - 0.5;

// ❌ DO NOT: Non-deterministic
const nonDet = (() => {
  let x = 0;
  return (a, b) => (x++, a - b);
})();

// ❌ DO NOT: Side effects
const withSideEffect = (a, b) => {
  console.log(a, b);  // Side effect
  return a - b;
};

// ❌ DO NOT: Throwing errors
const throws = (a, b) => {
  throw new Error('Oops');
};

// ❌ DO NOT: Inconsistent logic
const inconsistent = (a, b) => {
  return Math.random() > 0.5 ? a - b : b - a;
};

Memory Management

Structure Lifecycle

// ✅ Proper lifecycle management

// 1. Create with expected size
const tree = new RedBlackTree<number, object>();

// 2. Add items
for (const item of items) {
  tree.set(item.id, item);
}

// 3. Use structure
const value = tree.get(key);

// 4. Clean up when done
tree.clear();  // O(n) operation

// 5. Allow garbage collection
tree = null;  // Or let it go out of scope

Garbage Collection

Library does NOT prevent garbage collection:

// JavaScript will GC unused structures
{
  const tree = new RedBlackTree();
  tree.addMany([...]);
  // tree goes out of scope
  // JavaScript automatically frees memory
}

// For browser memory management
function processLargeDataset() {
  const tree = new RedBlackTree();
  
  try {
    // Process data
    for (const item of dataset) {
      tree.set(item.id, item);
    }
    return tree.size;
  } finally {
    tree.clear();  // Explicit cleanup
  }
}

Node References

Be careful with cached references:

// ❌ Potential memory leak
const nodes = [];
for (const item of items) {
  const node = tree.getNode(item.id);
  nodes.push(node);  // Keeps reference
}

// Tree nodes hold references to their neighbors
// This prevents garbage collection

// ✅ Don't keep references to internal nodes
for (const item of items) {
  const value = tree.get(item.id);  // Get value, not node
  // Process value
}

Type Safety

Strict TypeScript Configuration

Recommended tsconfig.json:

{
  "compilerOptions": {
    "strict": true,
    "strictNullChecks": true,
    "strictFunctionTypes": true,
    "strictPropertyInitialization": true,
    "strictBindCallApply": true,
    "alwaysStrict": true,
    "noImplicitAny": true,
    "noImplicitThis": true,
    "noImplicitReturns": true,
    "noFallthroughCasesInSwitch": true,
    "noImplicitReturns": true
  }
}

Type-Safe Usage

// ✅ Type-safe
const tree = new RedBlackTree<number, string>();
tree.set(1, 'Alice');
const name = tree.get(1);  // Type: string | undefined

// ❌ Unsafe (avoided with strict mode)
const anyTree = new RedBlackTree() as any;
anyTree.set('wrong type', 123);  // TypeScript won't catch this

Generic Constraints

// ✅ Constrain types
interface Comparable {
  compareTo(other: this): number;
}

const tree = new RedBlackTree<Comparable>((a, b) => {
  return a.compareTo(b);
});

// ✅ Union types for flexibility
type ValidKey = number | string | symbol;
const tree = new RedBlackTree<ValidKey, unknown>();

Iteration Safety

Safe Iteration Patterns

Pattern 1: Snapshot before mutation

// ✅ SAFE: Create snapshot first
const tree = new RedBlackTree([1, 2, 3, 4, 5]);

const items = [...tree];  // Snapshot
items.forEach(item => {
  tree.delete(item);  // Safe to mutate now
});

Pattern 2: Collect then apply

// ✅ SAFE: Collect mutations first
const tree = new RedBlackTree([1, 2, 3, 4, 5]);

const toDelete = [];
for (const item of tree) {
  if (shouldDelete(item)) {
    toDelete.push(item);
  }
}

toDelete.forEach(item => tree.delete(item));  // Apply mutations

Pattern 3: Functional approach

// ✅ SAFE: Functional transformations
const tree = new RedBlackTree([1, 2, 3, 4, 5]);

const filtered = tree
  .filter(x => x > 2)
  .map(x => x * 2);

// Result is new structure, original unchanged

Unsafe Iteration

// ❌ DO NOT DO THIS
const tree = new RedBlackTree([1, 2, 3]);

for (const item of tree) {
  if (condition(item)) {
    tree.delete(item);  // Undefined behavior!
  }
}

// ❌ DO NOT DO THIS
const tree = new RedBlackTree([1, 2, 3]);

[...tree].forEach(item => {
  tree.set(item, 'new');  // May cause issues
});

Denial of Service (DoS) Protection

Attack Vector: Expensive Comparisons

Risk: Comparator is very slow

// ❌ Attacker provides slow comparator
const tree = new RedBlackTree<number>((a, b) => {
  // Simulate expensive operation
  for (let i = 0; i < 1000000; i++) {
    Math.sqrt(i);
  }
  return a - b;
});

tree.addMany([...1000 items...]);  // Takes forever

Mitigation:

// ✅ Set timeout for tree operations
function withTimeout<T>(fn: () => T, timeoutMs: number): T {
  const start = Date.now();
  const result = fn();
  
  if (Date.now() - start > timeoutMs) {
    throw new Error('Tree operation exceeded timeout');
  }
  
  return result;
}

// Usage
withTimeout(() => tree.addMany(items), 1000);

Attack Vector: Hash Collision

Risk: Malicious keys cause hash-like collisions

// This is not applicable to comparison-based trees
// Skip lists and other hash-based structures at risk

Attack Vector: Stack Overflow

Risk: Very deep recursive structure

// ❌ Create deeply unbalanced tree (if using unbalanced BST)
const bst = new BST();
for (let i = 0; i < 10000; i++) {
  bst.add(i);  // Creates linear chain, not balanced tree
}

// For balanced trees (RedBlackTree, AVLTree):
// ✅ Automatically balanced
const rbTree = new RedBlackTree();
for (let i = 0; i < 10000; i++) {
  rbTree.set(i, i);  // Always balanced, logarithmic depth
}

Dependency Security

No Runtime Dependencies

✅ Zero runtime dependencies

{
  "name": "data-structure-typed",
  "dependencies": {},
  "devDependencies": {
    "typescript": "^5.0.0",
    "jest": "^29.0.0"
  }
}

Benefit:

No supply chain attacks from dependencies
No security updates needed for dependencies
Smaller bundle size
No transitive dependency issues

Development Dependencies

All dev dependencies are security-audited:

npm audit  # Always clean (zero vulnerabilities)

Secure Usage Patterns

Pattern 1: Bounded Collections

class SafeTree<K, V> extends RedBlackTree<K, V> {
  private readonly maxSize: number;

  constructor(maxSize: number = 100000) {
    super();
    this.maxSize = maxSize;
  }

  set(key: K, value: V): this {
    if (this.size >= this.maxSize && !this.has(key)) {
      throw new Error(`Collection exceeds max size: ${this.maxSize}`);
    }
    return super.set(key, value);
  }
}

Pattern 2: Validated Input

function processUntrustedData(data: unknown): void {
  // 1. Validate structure
  if (!isArray(data)) {
    throw new TypeError('Expected array');
  }

  // 2. Validate items
  const validItems = data.filter(isValidItem);
  
  // 3. Use in structure
  const tree = new RedBlackTree<number, string>();
  
  for (const item of validItems) {
    tree.set(item.id, item.name);
  }
}

function isValidItem(item: unknown): item is { id: number; name: string } {
  return (
    typeof item === 'object' &&
    item !== null &&
    typeof (item as any).id === 'number' &&
    typeof (item as any).name === 'string'
  );
}

Pattern 3: Timeout Protection

async function processWithTimeout<T>(
  fn: () => T,
  timeoutMs: number
): Promise<T> {
  return Promise.race([
    Promise.resolve(fn()),
    new Promise<never>((_, reject) =>
      setTimeout(() => reject(new Error('Timeout')), timeoutMs)
    )
  ]);
}

// Usage
const tree = new RedBlackTree();
await processWithTimeout(() => {
  tree.addMany(items);
}, 5000);  // 5 second timeout

Pattern 4: Snapshot Operations

function batchDelete<K, V>(
  tree: RedBlackTree<K, V>,
  predicate: (v: V, k?: K) => boolean
): number {
  const snapshot = [...tree.entries()];
  let deleted = 0;

  for (const [key, value] of snapshot) {
    if (predicate(value, key)) {
      if (tree.delete(key)) {
        deleted++;
      }
    }
  }

  return deleted;
}

Known Limitations

Timing Attacks

Library is NOT constant-time:

// Search time depends on tree depth (logarithmic but variable)
tree.get(key);  // May take different times

// Use only in non-cryptographic contexts
// DO NOT use for cryptographic key storage

Stack Depth

Very large structures may cause stack issues with recursion-based operations:

// ❌ Risk: Deep tree with DFS
const largeTree = new RedBlackTree();
for (let i = 0; i < 1000000; i++) {
  largeTree.set(i, i);  // Very deep tree possible
}

// RedBlackTree maintains O(log n) depth, so safe
// BST without balancing could reach O(n) depth

Weak Comparators

Library trusts provided comparators:

// ❌ User error: Bad comparator
const tree = new RedBlackTree((a, b) => {
  return Math.random() - 0.5;  // Random!
});

// Library assumes comparator is deterministic
// User responsibility to provide valid comparator

Security Update Policy

Reporting Vulnerabilities

DO NOT open public GitHub issues for security vulnerabilities.

Instead:

Email: [email protected] (if applicable)
Or use GitHub Security Advisories private reporting
Include: Description, Impact, Proof of Concept, Suggested Fix

Response Timeline

Day 0: Initial acknowledgment
Day 1-3: Triage and impact assessment
Day 3-7: Fix development
Day 7-14: Testing and validation
Day 14: Security release published

Disclosure Policy

Responsible Disclosure:

90-day embargo before public disclosure
Fix released before public announcement
Credit to reporter (if desired)
CVE assignment for critical issues

Patch Release Schedule

Security patches released immediately as:

2.0.x - Current stable version
1.x.x - Extended support (if applicable)

Security Checklist

For Library Developers

✅ Run npm audit regularly
✅ Keep TypeScript updated
✅ Review all public APIs
✅ Test error handling
✅ Document security considerations
✅ Monitor GitHub Security Advisories

For Library Users

✅ Use strict TypeScript (strict: true)
✅ Validate all external input
✅ Bound structure sizes
✅ Don't mutate during iteration
✅ Provide valid, pure comparators
✅ Keep TypeScript updated

Additional Resources

SPECIFICATION.md - Technical specifications
ARCHITECTURE.md - Design decisions
PERFORMANCE.md - Performance characteristics
GUIDES.md - Usage examples
OWASP - https://owasp.org (security best practices)
CWE - https://cwe.mitre.org (weakness taxonomy)

Summary

data-structure-typed is secure for general-purpose use with these principles:

Trust TypeScript - Use strict mode for type safety
Bound Inputs - Enforce maximum sizes at application level
Validate Comparators - Ensure they're pure and deterministic
Snapshot Mutations - Never mutate during iteration
Monitor Usage - Track structure sizes and operation times

For cryptographic security: This is NOT the right library. Use dedicated crypto libraries like TweetNaCl.js, libsodium, or crypto-js.

Maintained By: @zrwusa
License: MIT
Last Updated: January 2026

Security: zrwusa/data-structure-typed

Security

SECURITY.md

SECURITY: data-structure-typed Security Guide

Table of Contents

Security Overview

Scope

Design Philosophy

Threat Model

Attack Vectors (In Scope)

1. Unintended Memory Growth

2. Comparator Exceptions

3. Iterator Mutation

4. Type Confusion

5. Infinite Loops

Security Guarantees

What This Library Guarantees

What This Library Does NOT Guarantee

Input Validation

Comparators Must Be Pure

Validate Comparators Upfront

Bound Structure Size

Comparator Safety

Comparator Requirements

Dangerous Comparators

Memory Management

Structure Lifecycle

Garbage Collection

Node References

Type Safety

Strict TypeScript Configuration

Type-Safe Usage

Generic Constraints

Iteration Safety

Safe Iteration Patterns

Unsafe Iteration

Denial of Service (DoS) Protection

Attack Vector: Expensive Comparisons

Attack Vector: Hash Collision

Attack Vector: Stack Overflow

Dependency Security

No Runtime Dependencies

Development Dependencies

Secure Usage Patterns

Pattern 1: Bounded Collections

Pattern 2: Validated Input

Pattern 3: Timeout Protection

Pattern 4: Snapshot Operations

Known Limitations

Timing Attacks

Stack Depth

Weak Comparators

Security Update Policy

Reporting Vulnerabilities

Response Timeline

Disclosure Policy

Patch Release Schedule

Security Checklist

For Library Developers

For Library Users

Additional Resources

Summary

There aren’t any published security advisories