# wireshark-0001: CWE-407 — O(n) linear scan over interesting_fields in dfilter membership test

**Severity:** MEDIUM
**File:** `epan/dfilter/dfilter.c:735-744` (`dfilter_interested_in_field`),
           `epan/dfilter/dfilter.c:748-782` (`dfilter_interested_in_proto`)
**Status:** PATCHED

## Description

`dfilter_interested_in_field()` and `dfilter_interested_in_proto()` perform a linear
scan over the `interesting_fields[]` plain `int` array to test whether a compiled
display filter references a given field ID.

During filter compilation, the interesting-fields set is correctly built using a
`GHashTable` (O(1) insert/lookup). At the end of compilation (`dfilter_compile`,
`dfilter.c:498`), the hash table is **converted to a plain `int[]` array** via
`dfw_interesting_fields()`. This discards the O(1) lookup capability.

At query time, every call to `dfilter_interested_in_field()` re-scans the entire
array linearly:

```c
// dfilter.c:735-744  — O(F) linear scan
for (i = 0; i < df->num_interesting_fields; i++) {
    if (df->interesting_fields[i] == hfid) {
        return true;
    }
}
```

This is called from `color_filters_use_hfid()` which iterates the entire color filter
list (`g_slist_find_custom`), giving O(C × F) total cost per field query when updating
color rules — where C = number of color filters and F = interesting fields per filter.

A complex display filter (e.g., `http`) can reference ~73 fields. A user with 20
color filters and one HTTP filter makes each `color_filters_use_hfid()` call O(20 × 73).
For `dfilter_interested_in_proto()` the cost is the same with an extra
`proto_registrar_is_protocol()` + `proto_registrar_get_parent()` call per element.

## Root Cause

```c
// dfilter.c:498 — compile time: hash -> array, discards O(1) lookup
dfilter->interesting_fields = dfw_interesting_fields(dfw, &dfilter->num_interesting_fields);

// dfilter.c:735 — runtime: O(F) linear scan instead of O(1) hash lookup
bool dfilter_interested_in_field(const dfilter_t *df, int hfid) {
    int i;
    for (i = 0; i < df->num_interesting_fields; i++) {
        if (df->interesting_fields[i] == hfid) return true;
    }
    return false;
}
```

## Fix

Retain the `GHashTable` in `dfilter_t` alongside (or replacing) the `int[]` array.
`dfilter_interested_in_field()` becomes a single `g_hash_table_contains()` call (O(1)).
The `int[]` iteration in `dfilter_prime_proto_tree()` (lines 715-717) is still needed
and already O(F) — that usage is correct and not affected.

## Patch

See `patch/wireshark-0001.patch`

## Benchmark

See `unit/WiresharkDfilterFieldTest.java` — C=20 color filters, F=100 interesting fields per filter:
- Slow (int[] linear scan): O(C × F) = 2,000 ops per query
- Fast (hash set): O(C × 1) = 20 ops per query
- Speedup: ~100×
