{"id":"CVE-2026-99567","summary":"assoc_array: don't chain a new shortcut onto an existing one","details":"In the Linux kernel, the following vulnerability has been resolved:\n\nassoc_array: don't chain a new shortcut onto an existing one\n\nWhen a full node's leaves and the new key all share the node's segment,\nassoc_array_insert_into_terminal_node() replaces the node with a\nshortcut to a pair of new nodes.  If the node is itself the target of a\nshortcut, the new shortcut is installed as that shortcut's next node,\nand a shortcut leading to a shortcut is something nothing expects:\nassoc_array_walk() indexes the second one as a node, and\nassoc_array_apply_edit() hits the BUG_ON() in the loop that adjusts\nnr_leaves_on_branch, on that same insertion.\n\nDeletion gets a node there.  When the subtree below a shortcut shrinks\nenough, assoc_array_delete() collapses it into one node below the\nshortcut, and the leaves it collects can all share that node's segment.\nThe next key that shares it too takes this path.  Eighteen insertions\nand a deletion are enough: sixteen keys that agree on bits 0-11, one\nthat leaves them at bit 8 and is deleted again, and one more that agrees\nwith the sixteen.\n\nHave the new shortcut replace the one in front of the node as well.\nassoc_array_insert_shortcut() gives it that shortcut's back pointer and\nparent slot, so the caller installs it where that one was, and excises\nthe old shortcut along with the node, which takes a second entry in\nexcised_meta[].  The new shortcut's index key comes from the new key up\nto the new skip level, so it covers what the old one did.\n\nFound by a userspace test doing random insertions and deletions on keys\nthat share long prefixes; a targeted case builds a shortcut, deletes\ndown to the collapse and inserts one more key.","modified":"2026-11-20T07:00:45.818274524Z","published":"2026-11-20T05:49:03.237Z","database_specific":{"cna_assigner":"Linux","osv_generated_from":"https://github.com/CVEProject/cvelistV5/tree/main/cves/2026/99xxx/CVE-2026-99567.json"},"references":[{"type":"PACKAGE","url":"https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git"},{"type":"WEB","url":"https://git.kernel.org/stable/c/258745fea55ba057c062e0e680a54fde26630e95"},{"type":"WEB","url":"https://git.kernel.org/stable/c/517e7bbfaf5381d47e8d393ff54c61107f8fb1bb"},{"type":"WEB","url":"https://git.kernel.org/stable/c/a7990a72267f264f5284f6bcb90d397b29ac00ed"},{"type":"ADVISORY","url":"https://github.com/CVEProject/cvelistV5/tree/main/cves/2026/99xxx/CVE-2026-99567.json"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-99567"}],"affected":[{"ranges":[{"type":"GIT","repo":"https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git","events":[{"introduced":"3cb989501c2688cacbb7dc4b0d353faf838f53a1"},{"fixed":"517e7bbfaf5381d47e8d393ff54c61107f8fb1bb"},{"fixed":"258745fea55ba057c062e0e680a54fde26630e95"},{"fixed":"a7990a72267f264f5284f6bcb90d397b29ac00ed"}]}],"database_specific":{"source":"https://storage.googleapis.com/cve-osv-conversion/osv-output/CVE-2026-99567.json"}},{"package":{"name":"Kernel","ecosystem":"Linux"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"3.13.0"},{"fixed":"6.12.118"}]},{"type":"ECOSYSTEM","events":[{"introduced":"6.13.0"},{"fixed":"6.18.64"}]},{"type":"ECOSYSTEM","events":[{"introduced":"6.19.0"},{"fixed":"7.3.5"}]}],"database_specific":{"source":"https://storage.googleapis.com/cve-osv-conversion/osv-output/CVE-2026-99567.json"}}],"schema_version":"1.9.2"}