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

/* 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:

/* 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:

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.

4 KiB Raw Permalink Blame History Unescape Escape