java-topology/docs/tickets/linux-0002-audit-filter-inodes-quadratic.md

linux-0002: audit_filter_inodes — O(F²R) names_list re-scan per syscall

File: kernel/auditsc.c Severity: HIGH — triggered on every syscall that touches audited inodes CWE: CWE-407 (Inefficient Algorithmic Complexity)

Call Chain

audit_filter_inodes()                   // called at syscall exit
  list_for_each_entry(n, ctx->names_list)  // O(F) — files touched by syscall
    audit_filter_inode_name(tsk, n, ctx)
      __audit_filter_op(tsk, ctx, inode_hash[h], name=n, op)
        list_for_each_entry_rcu(e, inode_hash[h])  // O(R/B) — rules in bucket
          audit_filter_rules(tsk, e->rule, ctx, name=n, ...)
            for (i < field_count)           // O(fields per rule)
              case AUDIT_INODE:
              case AUDIT_DEVMAJOR:
              case AUDIT_DEVMINOR:
              case AUDIT_OBJ_UID:
              case AUDIT_OBJ_GID:
              case AUDIT_OBJ_USER:
                if (!name) {
                  list_for_each_entry(n, ctx->names_list)  // O(F) again
                }

audit_filter_rules is called with the current name pointer (non-NULL), so the inner ctx->names_list re-scan at lines 572–624 is guarded by else if (ctx).

However audit_filter_syscall invokes __audit_filter_op(..., name=NULL, ...) over the AUDIT_FILTER_EXIT list — a flat list, not the inode hash. For every rule in that list whose fields include AUDIT_INODE, AUDIT_DEVMAJOR, or the object ownership types, the inner list_for_each_entry(n, ctx->names_list) fires unconditionally:

audit_filter_syscall()
  __audit_filter_op(tsk, ctx, &audit_filter_list[AUDIT_FILTER_EXIT], name=NULL, op)
    list_for_each_entry_rcu(e, list)     // O(R) rules
      audit_filter_rules(..., name=NULL) // inner names_list scan O(F) per inode-field

Total per-syscall cost: O(R × fields × F) where R = audit rules on EXIT list, F = files touched per syscall. For a process that opens many files under a directory audit watch (e.g., recursive compiler invocation), both R and F grow independently and the product becomes dominant.

Reproducing the Quadratic Growth

A process issuing N open() calls under an auditctl -w /path -p rwxa watch triggers O(N × R) comparisons. With 100 audit rules and a syscall touching 100 files, that is 10,000 comparisons instead of 200.

Root Cause

audit_filter_rules() cannot match a specific field value against "any file in ctx" without re-walking ctx->names_list. Because it is called per-rule rather than per-name, and both R and F are unbounded, the combination is O(R × F).

Fix

Two complementary approaches:

A. Pass name=current_n from audit_filter_inodes path (already done — correct). The audit_filter_syscall path should similarly avoid the O(F) inner scan by only checking rules that carry per-name field types via the inode hash, not the flat EXIT list.

B. For the EXIT list path (audit_filter_syscall): pre-compute a per-context bitset of observed dev/ino values into the audit_context at name-collection time. Rules with AUDIT_INODE/AUDIT_DEVMAJOR etc. can then be checked in O(1) via bitset membership rather than rescanning names_list.

/* In struct audit_context, add: */
struct {
    unsigned long ino_mask[BITS_TO_LONGS(AUDIT_INODE_BUCKETS)];
    u32 devmajor_set[4];   /* sparse bitset for seen majors */
} fast_filter;

Set bits at __audit_inode() time; check bits in audit_filter_rules() before the list_for_each_entry fallback.

Impact

• Every open(2) / openat(2) under a directory watch runs O(R×F) comparisons.
• Compiler invocations (gcc, clang) touch hundreds of headers → audit load spikes.
• Scales linearly with both rule count and file count — O(n²) in the worst case.

Patch

See defects/linux/patch/linux-0002-audit-filter-inodes-quadratic.patch