russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
79 lines
2.1 KiB
ReStructuredText
79 lines
2.1 KiB
ReStructuredText
Linux Kernel — CWE-407 Analysis
|
|
=================================
|
|
|
|
.. contents:: :local:
|
|
|
|
Overview
|
|
--------
|
|
|
|
The Linux kernel source tree includes build-time tooling written in Perl for detecting circular
|
|
``#include`` dependencies in header files. One CWE-407 defect site was found in
|
|
``scripts/headerdep.pl``. It is unpatched. This is a MEDIUM-severity defect: it runs at kernel
|
|
build time, not at runtime, and input is bounded by the number of kernel headers.
|
|
|
|
Defect Sites
|
|
------------
|
|
|
|
linux-0001
|
|
~~~~~~~~~~
|
|
|
|
**File:** ``scripts/headerdep.pl:153``
|
|
|
|
**Pattern:**
|
|
|
|
.. code-block:: perl
|
|
|
|
# BFS cycle detection — grep on @$top array
|
|
sub find_cycles {
|
|
my ($top, $header) = @_;
|
|
if (grep { $_ eq $header } @$top) { # O(|$top|) — grep traverses list
|
|
return 1; # cycle found
|
|
}
|
|
push @$top, $header;
|
|
# ... recurse through includes
|
|
}
|
|
|
|
**Why this is O(n):** Perl ``grep { $_ eq $header } @$top`` is a linear scan; called once
|
|
per header during BFS traversal.
|
|
|
|
**Complexity:** ``O(V²)`` where V = number of header files in the include graph (MEDIUM —
|
|
bounded by kernel header count, build-time only)
|
|
|
|
**Patch:**
|
|
|
|
.. code-block:: perl
|
|
|
|
sub find_cycles {
|
|
my ($top_list, $top_set, $header) = @_;
|
|
if (exists $top_set->{$header}) { # O(1) hash lookup
|
|
return 1;
|
|
}
|
|
$top_set->{$header} = 1;
|
|
push @$top_list, $header;
|
|
# ... recurse through includes
|
|
pop @$top_list;
|
|
delete $top_set->{$header};
|
|
}
|
|
|
|
**Data structure change:** ``@array`` + ``grep`` → ``%hash`` + ``exists``
|
|
|
|
**Status:** Unpatched
|
|
|
|
Benchmark Results
|
|
-----------------
|
|
|
|
.. TODO: benchmark pending patch
|
|
|
|
Complexity Proof
|
|
----------------
|
|
|
|
Let V = header files in the traversal. ``grep { $_ eq $header } @$top`` on an array of up to V
|
|
elements: O(V) per call. With V calls: O(V²). Perl hash ``exists`` is O(1) amortized: O(V)
|
|
total. QED.
|
|
|
|
References
|
|
----------
|
|
|
|
* Defect ticket: ``tools/tickets/defects/linux-0001.md``
|
|
* Note: this defect affects kernel developer tooling (``make headers_check``,
|
|
``make headerdep``), not the kernel itself at runtime.
|