Regex Dos in Dynamodb
How Regex Dos Manifests in Dynamodb
Regular expression denial of service (ReDoS) attacks in DynamoDB contexts exploit the way DynamoDB's query and scan operations process filter expressions. When user-controlled input is used to construct regular expressions for DynamoDB's FilterExpression or ConditionExpression parameters, attackers can craft inputs that cause exponential backtracking, consuming excessive CPU resources.
The vulnerability typically manifests when applications use client-provided values to build regex patterns for filtering query results. For example, a search endpoint might allow users to search for items containing specific patterns:
const params = {
TableName: 'Products',
FilterExpression: 'contains(#name, :name)',
ExpressionAttributeNames: {'#name': 'name'},
ExpressionAttributeValues: {':name': {S: userInput}}
};If the application later uses this value to construct a regex for additional processing, or if DynamoDB's own regex evaluation (in certain configurations) is involved, the attack surface expands. The most dangerous patterns are those with nested quantifiers like (a+)+, (a*)*, or alternations with overlapping matches like (a|aa)*b.
In DynamoDB contexts, the risk is amplified because:
- Scan operations read entire tables, making them expensive even before regex processing
- Filter expressions are evaluated client-side after data retrieval
- Large datasets combined with malicious patterns can exhaust memory
- Service quotas may be exceeded, causing legitimate requests to fail
A practical attack might involve searching for products with names matching a crafted pattern that takes seconds or minutes to evaluate, effectively creating a denial of service for the DynamoDB table.
Dynamodb-Specific Detection
Detecting regex DoS vulnerabilities in DynamoDB applications requires examining both the application code and the runtime behavior. Static analysis should focus on identifying where user input flows into regex construction or DynamoDB filter expressions.
Key detection patterns include:
// Vulnerable pattern - direct interpolation of user input
const regex = new RegExp(userInput);
const filtered = items.filter(item => regex.test(item.name));Using middleBrick's API security scanner, you can detect these vulnerabilities by scanning your API endpoints. The scanner tests for regex DoS by submitting crafted payloads designed to trigger exponential backtracking in regex evaluation paths.
middleBrick's detection methodology includes:
- Testing for common malicious regex patterns in query parameters
- Analyzing how user input is incorporated into DynamoDB expressions
- Measuring response time variations with different input patterns
- Checking for proper input validation and sanitization
The scanner specifically looks for DynamoDB patterns like:
// Patterns that middleBrick tests for:
const maliciousPatterns = [
'(a+)+', // Nested quantifiers
'(a*)*', // Multiple nested quantifiers
'(a|aa)*b', // Overlapping alternations
'([a-zA-Z]+)*$', // Character class with nested quantifiersmiddleBrick's LLM security module also checks for AI-specific regex vulnerabilities, testing how LLM-powered search features handle regex patterns in DynamoDB queries, protecting against both traditional ReDoS and AI-specific prompt injection attacks that could manipulate regex behavior.
Dynamodb-Specific Remediation
Remediating regex DoS vulnerabilities in DynamoDB applications requires a defense-in-depth approach. The primary strategies involve input validation, safe regex construction, and architectural changes to how filtering is performed.
First, implement strict input validation before any regex processing:
function validateSearchInput(input) {
// Allow only alphanumeric and basic punctuation
const allowedPattern = /^[a-zA-Z0-9\s.,-]*$/;
if (!allowedPattern.test(input)) {
throw new Error('Invalid search characters');
}
// Limit length to prevent large pattern attacks
if (input.length > 50) {
throw new Error('Search term too long');
}
return input;
}For DynamoDB-specific filtering, use the service's built-in capabilities rather than client-side regex:
// Safe DynamoDB filtering using built-in operators
const params = {
TableName: 'Products',
FilterExpression: 'contains(#name, :name) AND begins_with(#category, :category)',
ExpressionAttributeNames: {'#name': 'name', '#category': 'category'},
ExpressionAttributeValues: {
':name': {S: userInput},
':category': {S: categoryFilter}
}
};Consider using DynamoDB's Global Secondary Indexes (GSI) for common search patterns instead of client-side filtering:
// Use GSI for efficient filtering
const params = {
TableName: 'Products',
IndexName: 'CategoryIndex',
KeyConditionExpression: '#category = :category',
ExpressionAttributeNames: {'#category': 'category'},
ExpressionAttributeValues: {':category': {S: categoryFilter}}
};For cases where regex is absolutely necessary, use libraries with safeguards:
import safeRegex from 'safe-regex';
function createSafeRegex(pattern) {
const isSafe = safeRegex(pattern);
if (!isSafe) {
throw new Error('Pattern too complex');
}
return new RegExp(pattern);
}Implement timeout mechanisms for regex operations:
function safeRegexTest(regex, input, timeout = 100) {
return new Promise((resolve, reject) => {
const timer = setTimeout(() => {
reject(new Error('Regex timeout'));
}, timeout);
try {
const result = regex.test(input);
clearTimeout(timer);
resolve(result);
} catch (error) {
clearTimeout(timer);
reject(error);
}
});
}middleBrick's CLI tool can help verify these remediations by scanning your updated endpoints and providing security scores for each fix implemented.
Related CWEs: inputValidation
| CWE ID | Name | Severity |
|---|---|---|
| CWE-20 | Improper Input Validation | HIGH |
| CWE-22 | Path Traversal | HIGH |
| CWE-74 | Injection | CRITICAL |
| CWE-77 | Command Injection | CRITICAL |
| CWE-78 | OS Command Injection | CRITICAL |
| CWE-79 | Cross-site Scripting (XSS) | HIGH |
| CWE-89 | SQL Injection | CRITICAL |
| CWE-90 | LDAP Injection | HIGH |
| CWE-91 | XML Injection | HIGH |
| CWE-94 | Code Injection | CRITICAL |