KaliBench: A Fine-Grained Benchmark for Cybersecurity Tool Use on Kali Linux with Runtime-Free Verifiable Rewards

KaliBench: Fine-Grained Cybersecurity Tool-Use Benchmark§

Motivation & Problem Formulation§

LLMs are increasingly tasked with translating analyst intent into concrete command-line invocations. Existing cybersecurity benchmarks evaluate either static knowledge or end-to-end agentic behavior, but neither directly measures the model's ability to emit executable commands for real security tools. The failure mode is brittle: a single misordered flag, wrong value binding, or syntax slip renders the invocation invalid. KaliBench frames this as a structured natural-language → CLI translation problem over the Kali Linux tool ecosystem.

Formally, given a query $q$ in natural language and a tool inventory $\mathcal{T}$, the model must produce a command $c$ such that:

$$\hat{c} = \arg\max_{c} p_\theta(c \mid q), \quad \text{subject to } \text{exec}(c) \neq \emptyset,\ \text{canon}(c) = \text{canon}(c^*)$$

where $c^*$ is the gold command, $\text{exec}$ is sandboxed execution, and $\text{canon}$ is deterministic canonicalization (whitespace, flag ordering, alias resolution).

Dataset Construction & Verification Pipeline§

KaliBench contains 8,504 query–command pairs spanning 1,642 tools, organized along 23 capability dimensions and 5 security phases (recon, scanning, exploitation, post-exploitation, reporting). Three mechanisms ensure quality:

1. Manuscript-grounded pipeline — commands are extracted from authoritative tool documentation, then deterministically canonicalized to remove surface-form variance (aliases like -h vs --help, redundant whitespace, equivalent orderings).
2. Alias-aware evaluation — scoring credits semantically equivalent invocations, preventing spurious penalties for valid alias choices.
3. Multi-stage verification — LLM-based validation, sandboxed terminal execution, and human-in-the-loop refinement are chained so every gold pair is both semantically correct and practically runnable.

Runtime-Free Verifiable Rewards§

A key contribution is that the deterministic canonicalization + alias-aware matching yield a reward signal without execution at training time. For a candidate command $c$ predicted from query $q$:

$$R(c, c^) = \alpha \cdot \mathbb{1}[\text{tool}(c) = \text{tool}(c^)] + \beta \cdot \frac{|F(c) \cap F(c^)|}{|F(c) \cup F(c^)|} + \gamma \cdot \mathbb{1}[\text{canon}(c) = \text{canon}(c^*)]$$

Here $F(\cdot)$ extracts the set of flag–value bindings, and the Jaccard term provides a graded partial-credit signal for argument construction when the exact command is not matched. This makes the reward cheap (no sandbox spin-up) yet verifiable and stable for RLVR.

Results & Training§

The authors evaluate 24 configurations of general-purpose and security-focused open-weight models across three evaluation modes (with/without tool hints, restricted flag set). In the unrestricted, no-hint setting, no open-weight model exceeds 42% exact-command accuracy. Supervised fine-tuning and reinforcement learning with the verifiable rewards derived from KaliBench significantly improve an 8B model, matching a 685B MoE baseline — evidence that dense, canonical reward signals substitute effectively for raw scale on this tool-use task.

import torch, torch.nn.functional as F

def verifiable_reward(pred, gold, w=(0.3, 0.3, 0.4)):
    # pred/gold: dicts {'tool': str, 'flags': set[(flag,value)]}
    tool_match = float(pred['tool'] == gold['tool'])
    fp, fg = pred['flags'], gold['flags']
    jac = len(fp & fg) / max(len(fp | fg), 1)
    exact = float(canon(pred) == canon(gold))
    a, b, g = w
    return a * tool_match + b * jac + g * exact

def grpo_step(policy, tokenizer, prompts, golds, opt, beta=0.04):
    # sample G completions per prompt
    G = 8
    with torch.no_grad():
        eps = torch.randn_like(policy.logits)  # simplified policy noise
    rewards = torch.tensor([
        verifiable_reward(parse(tok.decode(s)), g)
        for p, g in zip(prompts, golds) for s in sample_G(policy, p, G)
    ])
    # group-normalized advantages (GRPO)
    adv = (rewards - rewards.mean()) / (rewards.std() + 1e-6)
    loss = -adv * policy.logprob_sum + beta * kl_to_ref(policy)
    loss.backward(); opt.step(); opt.zero_grad()

@torch.no_grad()
def sample_G(policy, prompt, G):
    return policy.generate(prompt, num_return_sequences=G, do_sample=True, temperature=0.8)

Takeaways§

KaliBench reframes cybersecurity tool use as a deterministic, canonicalizable structured-prediction problem. The conversion of brittle CLI syntax into exact-match-plus-Jaccard rewards unlocks RLVR at low cost, and the empirical result — 8B ≈ 685B — argues that reward density, not parameter count, drives command-level cybersecurity competence. The benchmark is released as both an evaluation suite and a training substrate.