I accidentally turned LLM memory into program analysis

Over the past few months, the author has been experimenting with Large Language Models (LLMs) for vulnerability research. LLMs are increasingly adept at navigating large codebases, explaining unfamiliar subsystems, and assisting in exploring potential attack surfaces. However, the model often loses track of established facts during lengthy investigations.

It may suggest approaches that have already been ruled out, forget false assumptions, or continue reasoning from invalid observations. This prompted the author to explore memory systems to improve LLMs for complex vulnerability research and reduce hallucinations.

The author initially looked into existing memory solutions for LLMs, which typically involve storing past conversations or observations, embedding them, and retrieving relevant pieces when needed. While this works reasonably well, the author found it unsatisfying. During a vulnerability research session, the model shouldn't just remember what was said but maintain the current knowledge.

For instance, if the author establishes that an attacker can control a kernel object, a normal memory system would store this observation and retrieve it when asked about the exploitability of the bug. However, if two hours later, the author discovers that object_a does not actually point to object_b due to a wrong assumption, the memory may contain the incorrect information.

The author realized that program analysis often involves maintaining a set of facts about a program and deriving additional facts from them using rules. They could define a rule stating that if one function calls another function, which in turn can reach a third function, then the first function can reach the third function as well.

Eventually, they calculate a fixed point containing everything derivable from the program. If an input fact changes, there are techniques to update only the affected results instead of rerunning everything from scratch. The author wanted a similar approach for LLMs during vulnerability research. If an observation changes, the model should automatically invalidate the affected conclusions instead of reconstructing the entire investigation.

This led the author to wonder why LLMs had to repeatedly rebuild their state during the investigation. This is how they ended up developing a Datalog engine for LLMs. Datalog is a declarative logic programming language that focuses on describing facts and rules from which new facts can be derived, rather than providing instructions for calculating something. The author stored facts and rules related to the investigation, such as:

controls_kernel_object(attacker)

object_a points to object_b

From these facts, the Datalog engine can derive additional conclusions like:

controls_kernel_object(attacker) implies object_a points to object_b

If the observation that "object_a points to object_b" changes, the Datalog engine can automatically invalidate the conclusion that "controls_kernel_object(attacker)" depends on this observation. This approach is more efficient than prompting the LLM to figure out the consequences of the changed observation.

The author split the problem into two parts: the LLM is still responsible for understanding natural language, source code, and debugger output. However, once the information is converted into structured facts, the Datalog database can maintain the knowledge instead of the model. Removing facts in a Datalog database is more complex than adding them.

If a fact has multiple supporting reasons, removing one reason doesn't invalidate the fact. For example, if fact c is derived from both a and b, removing a doesn't remove c because b provides another derivation. This is crucial during vulnerability research because a conclusion may be supported by multiple observations. If one exploit primitive turns out not to work, other independent paths to the same result may remain true.

The Lemmalog engine keeps track of how facts are derived and updates their support when changes occur. It also allows the model to request the provenance of a conclusion, which provides a conceptual explanation of why the conclusion was reached. If observation_41 later turns out to be incorrect, Lemmalog can remove the affected conclusions automatically, as it knows the dependencies of the derived facts.

This solves the problem of LLMs reconstructing their entire state during the investigation and allows for more efficient and accurate vulnerability research.