RelShield: Maximally Permissive Shields for Tool-Using Agents over Relational Data

Tool-using language agents can automate business processes without hard-coding a separate control flow for every user request, but they must still satisfy standing requirements over the data they modify. Existing guardrails typically enforce safety specifications over simplified views of application state, which may omit relationships needed to enforce them correctly. This can cause guardrails to permit unsafe calls or unnecessarily block safe ones. To alleviate this problem, we introduce RelShield, a novel shielding framework that synthesizes restrictions directly from a first-order safety requirement over the underlying relational application state, together with tool specifications, legal initial states, and uncontrollable environment actions. From these inputs, we provide the safety-game fixed point characterization of the maximally permissive shield, i.e., the largest set of grounded calls that can remain available at each state while guaranteeing that every execution preserves the requirement. We first prove that shield synthesis is undecidable in this relational setting, and then give a general sound symbolic synthesis procedure. For a class of instances whose reachable safe states have bounded size, we prove synthesis becomes decidable and give a sound and complete synthesis method. We implement both procedures in RelShield and evaluate them on relational instances constructed from three established tool-using agentic benchmarks. Under a fixed budget, RelShield successfully synthesizes the maximally permissive shield for 78.0% of instances. For 31.3% of solved instances, RelShield proves that no additional shield restrictions are needed, certifying that the environment itself enforces compliance. Finally, we compare against an LLM baseline and find that its synthesized shields fail to match those produced by RelShield on at least a third of instances.