Static taint analysis for LLM agents

The DeepClause Approach

I’ve been working on DeepClause, a tool that compiles Markdown descriptions into DML programs — a Prolog-based language for orchestrating LLM agents. You write what the agent should do in prose, the compiler produces a logic program, and the runtime executes it (e.g. basically DSPy + CodeAct + Prolog). While this might seem like a somewhat odd approach, this article describes how we can use this to our advabtage and build more secure agents.

Here’s a minimal DML program to give you the idea:

tool(run_code(Code, Output), "Execute code in a sandboxed VM") :-
    exec(vm_exec(code: Code), Output).

agent_main :-
    system("You are a helpful coding assistant."),
    input("What would you like to build?", UserMsg),
    user(UserMsg),
    task("Help the user with their coding request.", string(Response)),
    answer(Response).

A few things to notice about how data flows through this:

• tool/2 defines a tool that the LLM can call during a task. Here it wraps vm_exec — arbitrary code execution in a sandboxed VM. The LLM decides when to call it and what arguments to pass. Those arguments are untrusted.

• system/1 sets the system prompt — the instruction the LLM sees first. It shapes everything the model does.

• input/2 prompts the user and binds their response to UserMsg. This is external, untrusted text.

• user/1 adds that text to the conversation memory. From this point on, every subsequent task/N call inherits it as context.

• task/N sends the accumulated memory (system prompt + user messages) to the LLM and gets a response. During execution, the LLM can call any defined tool/2 — and the arguments it passes are shaped by everything in its context, including the tainted user message. The response itself is also untrusted.

So there are at least three categories of untrusted data flowing through a typical agent: parameters from the caller, direct user input, and LLM outputs. If any of them reach a sensitive operation — injecting into the system prompt, executing code, calling external APIs — you have a potential attack surface.

This is the same class of problem that Google’s CaMeL paper (Debenedetti et al., 2025) tackles with runtime taint tracking: they wrap a protective layer around the LLM that separates control flow from data flow, preventing untrusted content from influencing program behavior. It’s a good approach. But because DML compiles to a real language with formal semantics, we can do something complementary: catch these flows statically using taint analysis. This can be done at compile time, before the agent ever runs.

This post explains how that works.

Source-Sink Tracking

The idea behind taint analysis is borrowed from traditional security research (SQL injection, XSS — same family of bugs). You identify sources (places where untrusted data enters the system) and sinks (places where that data can cause harm). Then you track whether tainted data can flow from any source to any sink.

In DeepClause, sources are:

• param/2 — parameters passed in from outside

• input/2 — direct user input

• user/1 — user messages added to memory

• Task outputs — anything an LLM generates (yes, LLM output is untrusted too)

• Tool and agent arguments — data flowing through exec/2

And sinks are:

• system/1 — the system prompt (severity: high). Tainted data here means prompt injection.

• exec/2 with dangerous tools — executing code via vm_exec, shell_exec, or eval (severity: critical). Tainted data here means command injection.

• task/N memory — when a task inherits tainted conversation history (severity: medium). More subtle, but still a vector.

The analyzer walks through every clause in your DML program and builds a map of which variables are tainted and how they flow.

Implementing This in Prolog

The nice thing about DML being Prolog is that the analyzer is also Prolog — and Prolog turns out to be unusually well-suited for this kind of work. Taint propagation is just pattern matching over terms: if a format/3 call contains a tainted variable, its output variable is tainted. If an assignment X = Y has a tainted right-hand side, X is tainted. If a string_concat involves a tainted argument, the result is tainted. Each of these rules is a single Prolog clause. The analyzer applies them in a fixed-point loop — keep propagating until nothing new gets tainted — which handles multi-hop chains automatically. A tainted parameter that flows through a format call, into an assignment, through a concat, into another assignment, and finally into an exec call gets caught regardless of how many intermediate steps there are.

What makes this particularly clean is that Prolog’s backtracking gives you exhaustive search for free. The analyzer doesn’t need to manually enumerate paths — it defines what a vulnerability looks like (tainted variable reaching a sink), and Prolog finds every instance. The entire thing — source identification, propagation, sink checking at three severity levels, capability extraction — is about 200 lines. Tools like FlowDroid or CodeQL solve the same class of problem in tens of thousands of lines, though to be fair, they handle reflection, callbacks, and async flows in general-purpose languages. For a DSL like DML, Prolog’s pattern matching is enough.

Prolog itself does not have global variables, therefore the DeepClause meteinterpreter has to track the LLM memory across the execution. This lets us extend the analyzer to catch implicit taint through memory. When user(UserMsg) adds untrusted input to the conversation history and a subsequent task() inherits that history, the analyzer flags it as a medium-severity risk — the LLM will see the tainted message in its context. Combined with tainted data in system(), an attacker can control both the system prompt and the user context pontentially injecting unwanted instructions into the prompt.

Two Layers of Defense

Static analysis catches the obvious stuff at compile time. But some vulnerabilities only make sense in context — is this tool supposed to have access to user data? Is this system prompt intentionally parameterized?

So DeepClause also has an LLM-based audit layer. After the static analyzer runs, you can optionally pass its findings to a language model configured as a “senior security engineer.” The LLM gets the code, the static analysis warnings, and the detected capabilities, and it writes a security report.

const result = await compileToDML(source, {
  analyze: true,   // Run static analysis
  audit: true,     // Run LLM security audit
  model: 'gpt-4o',
  provider: 'openai'
});

if (result.analysis?.warnings.length) {
  console.log('Security warnings:', result.analysis.warnings);
}
if (result.analysis?.auditorReport) {
  console.log('Audit report:', result.analysis.auditorReport);
}

Two different tools for two different jobs. Prolog handles the data flow analysis — deterministic, exhaustive. The LLM handles the contextual judgment. They complement each other nicely.

What’s Next

The analyzer is still young. There are things I want to add:

• Inter-procedural analysis: Right now each clause is analyzed independently. Tracking taint across predicate calls would catch more complex flows.

• Sanitization detection: If you explicitly validate or sanitize input before using it, the analyzer should recognize that and suppress the warning.

• Configurable policies: Different agents have different threat models. A public-facing chatbot needs stricter checks than an internal automation tool.

---

If you want to try it, the analysis runs automatically when you compile with the --analyze flag:

deepclause compile my-agent.md --analyze

Or programmatically:

import { analyzeDML } from 'deepclause-sdk';

const result = await analyzeDML(dmlCode);
for (const warning of result.warnings) {
  console.log(`[${warning.level.toUpperCase()}] ${warning.message}`);
}

The code is open source. The analyzer is ~200 lines of Prolog. If you find a taint flow it misses, I’d genuinely love to hear about it.

---

This is part of an ongoing series about building DeepClause — a framework that compiles Markdown specs into executable logic programs. Previous post: Compiled Specs.