Duplicate Key in Associative List (Alist)

Description

Duplicate Key in Associative List is a vulnerability where an associative list (dictionary, map, or similar data structure) contains multiple entries with the same key. While duplicate key entries could theoretically serve as a constant-time replacement function when properly designed, they often occur unintentionally. This ambiguity creates confusion about whether non-unique keys represent an actual error condition, leads to unpredictable behavior depending on which entry is accessed, and can cause subtle security issues when the wrong value is retrieved for a key.

Risk

Duplicate keys in associative lists create unpredictable behavior and potential security vulnerabilities. When code expects unique keys, retrieving a value may return an unexpected result depending on implementation details. Sorting operations become undefined. Security decisions based on lookups may use the wrong value. Configuration parsing with duplicate keys may apply unexpected settings. In JSON/XML processing, duplicate keys may allow parameter pollution attacks. The low likelihood of intentional exploitation is offset by the high likelihood of bugs causing security-relevant incorrect behavior.

Solution

Replace associative list implementations with hash tables or other structures that inherently enforce key uniqueness. Implement validation to check key uniqueness before each entry insertion. When parsing external data (JSON, configuration files), validate that no duplicate keys exist and reject or merge duplicates according to a clear policy. Use static analysis tools to detect potential duplicate key issues. When duplicate keys are legitimately needed, use multimap structures that explicitly support multiple values per key.

Common Consequences

Impact	Details
Other	Scope: Other Quality Degradation - Software behaves unpredictably when duplicate keys exist, as the retrieved value depends on implementation details.
Other	Scope: Other Varies by Context - Security impact depends on how the associative list is used. May cause incorrect authorization decisions or configuration errors.

Example Code

Vulnerable Code

# Vulnerable: Duplicate keys in configuration parsing
class VulnerableConfigParser:
    def parse_config(self, config_lines):
        config = {}

        for line in config_lines:
            key, value = line.strip().split('=', 1)
            # Vulnerable: Silently overwrites duplicates
            config[key] = value

        # Attacker provides:
        # admin_required=true
        # admin_required=false
        # Last value wins - security bypassed
        return config

    def parse_json_permissive(self, json_string):
        # Vulnerable: Python json module uses last-value-wins for duplicates
        import json
        return json.loads(json_string)

        # JSON: {"role": "user", "role": "admin"}
        # Result: {"role": "admin"} - privilege escalation

    def process_form_data(self, form_fields):
        # Vulnerable: Multiple values for same parameter
        params = {}
        for field in form_fields:
            # Vulnerable: Only stores last value
            params[field.name] = field.value

        # HTTP Parameter Pollution: ?admin=false&admin=true
        # May bypass security depending on implementation
        return params

// Vulnerable: Duplicate keys in property handling
public class VulnerablePropertyHandler {

    public Properties loadProperties(InputStream input) throws IOException {
        Properties props = new Properties();
        BufferedReader reader = new BufferedReader(new InputStreamReader(input));

        String line;
        while ((line = reader.readLine()) != null) {
            if (line.contains("=")) {
                String[] parts = line.split("=", 2);
                // Vulnerable: Later values overwrite earlier
                props.setProperty(parts[0], parts[1]);
            }
        }

        return props;
    }

    // Vulnerable: XML with duplicate attributes
    public Map<String, String> parseXMLAttributes(Element element) {
        Map<String, String> attrs = new HashMap<>();

        NamedNodeMap nodeMap = element.getAttributes();
        for (int i = 0; i < nodeMap.getLength(); i++) {
            Node attr = nodeMap.item(i);
            // Vulnerable: Depends on parser's handling of duplicates
            attrs.put(attr.getNodeName(), attr.getNodeValue());
        }

        return attrs;
    }
}

// Vulnerable: Duplicate entries in lookup table
#include <stdio.h>
#include <string.h>

typedef struct {
    char* key;
    char* value;
} Entry;

typedef struct {
    Entry* entries;
    int count;
    int capacity;
} AssocList;

// Vulnerable: No duplicate checking on insert
void vulnerable_insert(AssocList* list, const char* key, const char* value) {
    if (list->count >= list->capacity) {
        // Expand array...
    }

    // Vulnerable: Blindly adds entry even if key exists
    list->entries[list->count].key = strdup(key);
    list->entries[list->count].value = strdup(value);
    list->count++;

    // List may now have duplicate keys
}

// Vulnerable: First-match lookup
const char* vulnerable_lookup(AssocList* list, const char* key) {
    for (int i = 0; i < list->count; i++) {
        if (strcmp(list->entries[i].key, key) == 0) {
            return list->entries[i].value;  // Returns first match
        }
    }
    return NULL;

    // If duplicates exist, always returns first value
    // Attacker inserts early entry to override later security settings
}

// Vulnerable: Environment variable parsing
void parse_env_config(AssocList* config) {
    // Vulnerable: /proc/*/environ may have duplicate entries
    // Attacker-controlled environment can have duplicates
    FILE* env_file = fopen("/proc/self/environ", "r");
    // ... parse and insert without checking duplicates
}

// Vulnerable: Duplicate keys in object handling
class VulnerableObjectHandler {

    parseQueryString(queryString) {
        const params = {};

        queryString.split('&').forEach(pair => {
            const [key, value] = pair.split('=');
            // Vulnerable: Later values overwrite
            params[decodeURIComponent(key)] = decodeURIComponent(value);
        });

        // ?role=user&role=admin -> {role: "admin"}
        return params;
    }

    mergeObjects(obj1, obj2) {
        // Vulnerable: obj2 keys silently override obj1
        return {...obj1, ...obj2};

        // If obj2 is attacker-controlled, they can override any key
    }

    processHeaders(headerArray) {
        const headers = {};

        for (const header of headerArray) {
            // Vulnerable: Duplicate headers not handled consistently
            headers[header.name.toLowerCase()] = header.value;

            // HTTP allows multiple headers with same name
            // Different behavior than browsers/servers may expect
        }

        return headers;
    }
}

Fixed Code

# Fixed: Duplicate key detection and handling
class SecureConfigParser:
    def parse_config(self, config_lines, allow_duplicates=False):
        config = {}
        seen_keys = set()

        for line_num, line in enumerate(config_lines, 1):
            if '=' not in line:
                continue

            key, value = line.strip().split('=', 1)

            # Fixed: Detect duplicates
            if key in seen_keys:
                if not allow_duplicates:
                    raise ConfigError(
                        f"Duplicate key '{key}' at line {line_num}"
                    )
                else:
                    # Fixed: Explicit policy for duplicates
                    # Option 1: Keep first value
                    continue
                    # Option 2: Merge into list
                    # if not isinstance(config[key], list):
                    #     config[key] = [config[key]]
                    # config[key].append(value)

            config[key] = value
            seen_keys.add(key)

        return config

    def parse_json_strict(self, json_string):
        import json

        # Fixed: Detect duplicate keys in JSON
        def detect_duplicates(pairs):
            seen = set()
            result = {}
            for key, value in pairs:
                if key in seen:
                    raise ValueError(f"Duplicate key in JSON: {key}")
                seen.add(key)
                result[key] = value
            return result

        return json.loads(json_string, object_pairs_hook=detect_duplicates)

    def process_form_data(self, form_fields):
        # Fixed: Handle multiple values explicitly
        from collections import defaultdict

        params = defaultdict(list)
        for field in form_fields:
            params[field.name].append(field.value)

        # Fixed: Return with explicit multi-value support
        # Or convert single values: {k: v[0] if len(v)==1 else v for k,v in params.items()}
        return dict(params)

// Fixed: Duplicate key prevention
public class SecurePropertyHandler {

    public Map<String, String> loadProperties(InputStream input) throws IOException {
        Map<String, String> props = new HashMap<>();
        Set<String> seenKeys = new HashSet<>();
        BufferedReader reader = new BufferedReader(new InputStreamReader(input));

        String line;
        int lineNumber = 0;
        while ((line = reader.readLine()) != null) {
            lineNumber++;
            if (line.contains("=")) {
                String[] parts = line.split("=", 2);
                String key = parts[0].trim();

                // Fixed: Check for duplicates
                if (seenKeys.contains(key)) {
                    throw new DuplicateKeyException(
                        "Duplicate key '" + key + "' at line " + lineNumber
                    );
                }

                props.put(key, parts[1]);
                seenKeys.add(key);
            }
        }

        return Collections.unmodifiableMap(props);
    }

    // Fixed: Validate uniqueness after parsing
    public void validateUniqueKeys(Map<String, ?> map, String context) {
        // For maps that might have been created from sources allowing duplicates
        // Validate the source before conversion
    }

    // Fixed: Use MultiMap for legitimate multi-value cases
    public Multimap<String, String> parseHeaders(List<Header> headers) {
        Multimap<String, String> result = ArrayListMultimap.create();

        for (Header header : headers) {
            result.put(header.getName().toLowerCase(), header.getValue());
        }

        // Fixed: Explicitly supports multiple values per key
        return result;
    }
}

// Fixed: Associative list with duplicate prevention
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct {
    char* key;
    char* value;
} Entry;

typedef struct {
    Entry* entries;
    int count;
    int capacity;
} AssocList;

// Fixed: Check for duplicates before insert
int secure_insert(AssocList* list, const char* key, const char* value) {
    // Fixed: Check if key already exists
    for (int i = 0; i < list->count; i++) {
        if (strcmp(list->entries[i].key, key) == 0) {
            // Fixed: Return error for duplicate
            return -1;  // Key already exists
        }
    }

    if (list->count >= list->capacity) {
        // Expand array...
        int new_capacity = list->capacity * 2;
        Entry* new_entries = realloc(list->entries,
                                     new_capacity * sizeof(Entry));
        if (!new_entries) return -2;
        list->entries = new_entries;
        list->capacity = new_capacity;
    }

    list->entries[list->count].key = strdup(key);
    list->entries[list->count].value = strdup(value);
    list->count++;

    return 0;  // Success
}

// Fixed: Update existing or insert new
int secure_upsert(AssocList* list, const char* key, const char* value) {
    // First, try to update existing
    for (int i = 0; i < list->count; i++) {
        if (strcmp(list->entries[i].key, key) == 0) {
            free(list->entries[i].value);
            list->entries[i].value = strdup(value);
            return 1;  // Updated existing
        }
    }

    // Not found, insert new
    return secure_insert(list, key, value);
}

// Fixed: Use hash table for O(1) duplicate detection
#include <uthash.h>  // Or similar hash table library

typedef struct {
    char* key;
    char* value;
    UT_hash_handle hh;
} HashEntry;

typedef struct {
    HashEntry* table;
} SecureMap;

int secure_map_insert(SecureMap* map, const char* key, const char* value) {
    HashEntry* existing = NULL;
    HASH_FIND_STR(map->table, key, existing);

    if (existing) {
        return -1;  // Duplicate key
    }

    HashEntry* entry = malloc(sizeof(HashEntry));
    entry->key = strdup(key);
    entry->value = strdup(value);
    HASH_ADD_KEYPTR(hh, map->table, entry->key, strlen(entry->key), entry);

    return 0;
}

// Fixed: Duplicate key handling
class SecureObjectHandler {

    parseQueryString(queryString, options = {}) {
        const { allowDuplicates = false, mergeStrategy = 'array' } = options;
        const params = new Map();
        const seen = new Set();

        queryString.split('&').forEach(pair => {
            const [key, value] = pair.split('=').map(decodeURIComponent);

            if (seen.has(key)) {
                if (!allowDuplicates) {
                    throw new Error(`Duplicate query parameter: ${key}`);
                }

                // Fixed: Explicit merge strategy
                if (mergeStrategy === 'array') {
                    const existing = params.get(key);
                    if (Array.isArray(existing)) {
                        existing.push(value);
                    } else {
                        params.set(key, [existing, value]);
                    }
                } else if (mergeStrategy === 'first') {
                    // Keep first value
                } else if (mergeStrategy === 'last') {
                    params.set(key, value);
                }
            } else {
                params.set(key, value);
                seen.add(key);
            }
        });

        return Object.fromEntries(params);
    }

    mergeObjects(target, source, options = {}) {
        const { onConflict = 'error' } = options;
        const result = {...target};

        for (const [key, value] of Object.entries(source)) {
            if (key in result) {
                // Fixed: Handle conflicts explicitly
                switch (onConflict) {
                    case 'error':
                        throw new Error(`Key conflict: ${key}`);
                    case 'keep':
                        break;  // Keep target value
                    case 'override':
                        result[key] = value;
                        break;
                    case 'merge':
                        if (typeof result[key] === 'object' && typeof value === 'object') {
                            result[key] = this.mergeObjects(result[key], value, options);
                        } else {
                            result[key] = value;
                        }
                        break;
                }
            } else {
                result[key] = value;
            }
        }

        return result;
    }

    processHeaders(headerArray) {
        // Fixed: Use Map that preserves all values
        const headers = new Map();

        for (const header of headerArray) {
            const name = header.name.toLowerCase();

            if (headers.has(name)) {
                // Fixed: Append to existing (HTTP spec allows multiple)
                const existing = headers.get(name);
                headers.set(name, `${existing}, ${header.value}`);
            } else {
                headers.set(name, header.value);
            }
        }

        return headers;
    }
}

---

CVE Examples

No specific CVEs are listed in the MITRE database for this CWE. However, the pattern is related to:

• HTTP Parameter Pollution attacks
• JSON injection via duplicate keys
• Configuration parsing vulnerabilities

---

References

1. MITRE Corporation. "CWE-462: Duplicate Key in Associative List (Alist)." https://cwe.mitre.org/data/definitions/462.html
2. CERT C Secure Coding Standard. "ENV02-C. Beware of multiple environment variables with the same effective name."