# UNDF: UNDF-2026-000000351
# asterisk-0003: CDR Variable Merge O(B×V) Quadratic Membership Scan

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Component**: Call Detail Records (CDR)
- **Location**: `main/cdr.c`, function `cdr_object_create_public_records()`, ~line 1458

## Description

When publishing CDR records at call teardown, Asterisk merges party_b channel
variables into the CDR varshead. For each party_b variable, it performs a full
linear scan of `varshead` (already containing party_a variables) to check for
duplicates before inserting.

This is an O(B × V) operation where:
- B = number of party_b variables
- V = number of variables already in varshead (party_a variables)

In a dialplan with many channel variables (common in IVR-heavy or CRM-integrated
deployments), every call teardown pays this quadratic cost.

## Defective Code

```c
/* main/cdr.c ~line 1458 — cdr_object_create_public_records() */
AST_LIST_TRAVERSE(&it_cdr->party_b.variables, it_var, entries) {
    int found = 0;
    struct ast_var_t *newvariable;
    AST_LIST_TRAVERSE(&cdr_copy->varshead, it_copy_var, entries) {  /* O(V) per it_var */
        if (!strcasecmp(ast_var_name(it_var), ast_var_name(it_copy_var))) {
            found = 1;
            break;
        }
    }
    if (!found && (newvariable = ast_var_assign(ast_var_name(it_var), ast_var_value(it_var)))) {
        AST_LIST_INSERT_TAIL(&cdr_copy->varshead, newvariable, entries);
    }
}
```

## Fix

Build a `case-insensitive hash set` of already-present variable names before the
merge loop, then do O(1) membership checks:

```c
/* Build a hash set of existing variable names (lowercased) */
struct ao2_container *existing_names = ao2_container_alloc_hash(
    AO2_ALLOC_OPT_LOCK_NOLOCK, 0, 31, str_hash_fn, NULL, str_cmp_fn);

AST_LIST_TRAVERSE(&cdr_copy->varshead, it_copy_var, entries) {
    char *lower = ast_strdupa(ast_var_name(it_copy_var));
    ast_str_to_lower(lower);
    ao2_link(existing_names, lower);
}

AST_LIST_TRAVERSE(&it_cdr->party_b.variables, it_var, entries) {
    char *lower = ast_strdupa(ast_var_name(it_var));
    ast_str_to_lower(lower);
    if (!ao2_find(existing_names, lower, OBJ_SEARCH_KEY | OBJ_NOLOCK)) {
        struct ast_var_t *newvariable = ast_var_assign(
            ast_var_name(it_var), ast_var_value(it_var));
        if (newvariable) {
            AST_LIST_INSERT_TAIL(&cdr_copy->varshead, newvariable, entries);
            ao2_link(existing_names, lower);
        }
    }
}
ao2_ref(existing_names, -1);
```

Alternatively, since CDR variable counts are moderate (typically < 100), a
simpler approach uses `ast_hashtab` which is already available in Asterisk:

```c
struct ast_hashtab *seen = ast_hashtab_create(31, ast_hashtab_compare_strings_nocase,
    ast_hashtab_resize_java, ast_hashtab_newsize_java,
    ast_hashtab_hash_string_nocase, 0);

AST_LIST_TRAVERSE(&cdr_copy->varshead, it_copy_var, entries) {
    ast_hashtab_insert_safe(seen, (void *)ast_var_name(it_copy_var));
}
AST_LIST_TRAVERSE(&it_cdr->party_b.variables, it_var, entries) {
    if (!ast_hashtab_lookup(seen, ast_var_name(it_var))) {
        struct ast_var_t *newvariable = ast_var_assign(
            ast_var_name(it_var), ast_var_value(it_var));
        if (newvariable) {
            AST_LIST_INSERT_TAIL(&cdr_copy->varshead, newvariable, entries);
            ast_hashtab_insert_safe(seen, ast_var_name(it_var));
        }
    }
}
ast_hashtab_destroy(seen, NULL);
```

## Complexity

| Metric | Before | After |
|--------|--------|-------|
| Variable merge | O(B × V) | O(B + V) |
| Per-lookup | O(V) linear scan | O(1) hash lookup |

## Speedup Estimate

At V=50 party_a vars and B=50 party_b vars:
- Before: 50 × 50 = 2,500 strcmp operations
- After: 50 + 50 = 100 hash operations
- Ratio: ~25x

At V=200, B=200 (large IVR/CRM deployment):
- Before: 200 × 200 = 40,000 operations
- After: 400 operations
- Ratio: ~100x

The defect scales quadratically with the number of channel variables, which
grows with dialplan complexity and integration depth.
