Hard problems that reduce to document ranking | noperator (https://noperator.dev/posts/document-ranking-for-complex-problems/) (/assets/css/stylesheet.5cf4e1218b79c13e3fbba607a60f894e607d5fdd79efe3df3c386c7b2fcd2f34.css) (https://noperator.dev/favicon.ico) (https://noperator.dev/favicon-16x16.png) (https://noperator.dev/favicon-32x32.png) (https://noperator.dev/apple-touch-icon.png) (https://noperator.dev/safari-pinned-tab.svg)   (https://noperator.dev/) (noperator (Alt + H)) noperator      Hard problems that reduce to document ranking  (2025-02-24 00:00:00 +0000 UTC) February 24, 2025   There are two claims I’d like to make: LLMs can be used effectively1  for listwise (https://en.wikipedia.org/wiki/Learning_to_rank#Approaches) document ranking . Some complex problems can (surprisingly) be solved by (https://en.wikipedia.org/wiki/Reduction_(complexity)) transforming them into document ranking problems.  I’ve primarily explored both of these claims in the context of using patch diffing to locate N-day vulnerabilities—a sufficiently domain-specific problem that can be solved using general purpose language models as comparators in document ranking algorithms. I demonstrated at (https://youtu.be/IBuL1zY69tY?si=l27sUOaECO-o9QFW&t=1846) RVAsec ‘24 that listwise document ranking can be used to locate the specific function in a patch diff that actually fixes a vulnerability described by a security advisory, and later wrote on the (https://bishopfox.com/blog/raink-llms-document-ranking) Bishop Fox blog in greater defense of listwise ranking by publishing a (https://github.com/noperator/raink) command-line tool implementation (raink ) to prove the idea. The key insight is that instead of treating patch diffing as a complex problem requiring specialized security engineering knowledge, you can reframe it as ranking diffs (documents) by their relevance to a security advisory (query), applying proven document ranking techniques from information retrieval.   Using this technique, I proved at (https://www.youtube.com/live/aQyBRlu-cA4?si=3V79VdVmPO9D5WVW&t=260) DistrictCon ‘25 that GPT-4o mini could locate a fixed vulnerability in a haystack of over 1600 changed (and stripped!) functions in a patch—costing only 5 minutes and 30 cents to do so2  . Document ranking can be applied to other offensive security problems, like identifying candidate functions for fuzzing targets (in addition to using them for (https://blog.oss-fuzz.com/posts/introducing-llm-based-harness-synthesis-for-unfuzzed-projects/) auto-generating harnesses ), or prioritizing potential injection points in a web application for deeper testing. A few potentially powerful improvements to this technique: Analyze the top N ranked results, and then apply the same ranking algorithm to the analyses. Make the ranked results verifiable; e.g., for N-day vulnerabilities, use an LLM to generate an automatically testable proof-of-concept exploit3  .  Following Thomas Dullien’s FUZZING ‘24 keynote (https://www.youtube.com/watch?v=Jd1hItbf52k&t=95s) “Reasons for the Unreasonable Success of Fuzzing” , I’m inclined to give a similar talk—“Reasons for the Unreasonable Success of LLMs.” A few others have explored the idea of document ranking using LLMs, but favored the computationally complex pairwise ranking method while noting the challenges of the more efficient but yet-unimplemented listwise ranking method. See (https://blog.reachsumit.com/posts/2023/12/prompting-llm-for-ranking/) Prompting-based Methods for Text Ranking Using Large Language Models (Dec ‘23) and (https://arxiv.org/html/2306.17563v2) Large Language Models are Effective Text Rankers with Pairwise Ranking Prompting (Mar ‘24). ↩︎   DistrictCon slides (https://drive.google.com/file/d/1DsIsme23HTjTZYVLul-lWtTErKS9mZUy/view) here . ↩︎   See aforementioned DistrictCon talk for an example of o3‑mini‑high successfully generating an exploit for (https://bishopfox.com/blog/sonicwall-cve-2024-53704-ssl-vpn-session-hijacking) CVE-2024-53704 , an authentication bypass in SonicWall firewalls. ↩︎           (Go to Top (Alt + G))