Capability Safety as Datalog: A Foundational Equivalence

Each language version is independently generated for its own context, not a direct translation.

Stellen Sie sich vor, Sie sind der Sicherheitschef eines riesigen, sich ständig verändernden Roboterschwarms. Jeder Roboter hat bestimmte Fähigkeiten (z. B. „Tür öffnen", „Daten abrufen", „Licht einschalten"). Manchmal können zwei Fähigkeiten zusammen eine dritte, gefährliche Fähigkeit erzeugen, die keiner der Roboter allein hatte (z. B. „Tür öffnen" + „Daten abrufen" = „Geheime Datenbank knacken").

Ihre Aufgabe ist es, zu wissen: Welche Kombinationen von Fähigkeiten sind sicher, und welche führen in eine Katastrophe?

Bisher war diese Aufgabe wie das Lösen eines riesigen, chaotischen Puzzles, bei dem man bei jeder kleinen Änderung (ein neuer Roboter kommt hinzu, eine Fähigkeit wird entfernt) das gesamte Puzzle neu lösen musste. Das war langsam, teuer und ineffizient.

Dieses Papier von Cosimo Spera sagt nun etwas Revolutionäres: „Hören Sie auf, das Puzzle neu zu lösen. Wir haben herausgefunden, dass Ihr Sicherheitsproblem eigentlich ein ganz einfaches, logisches Rechenspiel ist, das wir seit 30 Jahren perfekt beherrschen."

Hier ist die Erklärung in einfachen Worten:

1. Der große „Aha!"-Moment: Vom Chaos zur Logik

Das Papier zeigt, dass das komplexe Netzwerk der Roboter-Fähigkeiten (das sogenannte „Capability Hypergraph") exakt dem entspricht, was Informatiker Datalog nennen.

Die Analogie: Stellen Sie sich Datalog wie ein riesiges, aber strenges Rezeptbuch vor.
- Ein Rezept lautet: „Wenn du Eier UND Mehl UND Zucker hast, dann kannst du Kuchen backen."
- In der Robotersicherheit heißt das: „Wenn Roboter A Schlüssel hat UND Roboter B Code hat, dann entsteht die Gefahr Einbruch."
Der Gewinn: Früher haben Sie diese Regeln manuell durchsucht. Jetzt wissen Sie: Das ist genau das, was Computer seit Jahrzehnten extrem schnell lösen können. Sie müssen kein neues mathematisches Universum erfinden; Sie können einfach die bestehenden, hochoptimierten Werkzeuge der Datenbank-Wissenschaft nutzen.

2. Der „Orts-Gap": Warum man nicht alles neu berechnen muss

Das ist der wichtigste praktische Teil des Papiers.

Das alte Problem: Wenn ein Roboter eine neue Fähigkeit bekommt, mussten Sie früher alle 10.000 anderen Roboter prüfen, um zu sehen, ob jetzt eine Gefahr droht. Das ist, als würden Sie, wenn Sie nur ein neues Gewürz in die Suppe geben, die gesamte Suppe neu kochen, nur um zu prüfen, ob sie schmeckt.
Die neue Lösung (DRed): Da wir wissen, dass es ein „Rezeptbuch" (Datalog) ist, können wir lokal arbeiten. Wenn Sie ein neues Gewürz hinzufügen, prüfen Sie nur die Schüsseln, die dieses Gewürz direkt betreffen.
Das Ergebnis: Das Papier beweist, dass diese neue Methode bei großen Systemen unendlich viel schneller ist als die alte Methode. Es ist der Unterschied zwischen „den ganzen Wald abholzen, um einen Baum zu prüfen" und „nur den Baum zu prüfen".

3. Der „Sicherheits-Schein" (Warum-Provenance)

Wenn ein Roboter eine gefährliche Fähigkeit entwickelt, wollen Sie nicht nur wissen, dass es passiert ist, sondern warum.

Die Analogie: Stellen Sie sich vor, ein Gericht ist verbrannt. Ein einfacher Bericht sagt: „Das Essen ist verbrannt." Ein Sicherheits-Schein (wie im Papier beschrieben) sagt: „Es ist verbrannt, weil Sie Salz (Roboter A) und Pfeffer (Roboter B) zusammen in die Pfanne getan haben, obwohl Sie wussten, dass das brennt."
Der Vorteil: Das Papier zeigt, dass man diese Beweise automatisch generieren, komprimieren und sogar für Audits (Prüfungen) nutzen kann. Es ist wie ein digitaler Fingerabdruck für jede Sicherheitsverletzung.

4. Warum das nicht trivial ist (Die „UND"-Falle)

Das Papier erklärt auch, warum das Problem so schwer war.

Die Analogie: Wenn eine Regel nur sagt: „Wenn du Apfel hast, kannst du Saft machen", ist das einfach. Aber wenn die Regel sagt: „Wenn du Apfel UND Birne UND Traube hast, explodiert die Küche", dann wird es kompliziert.
Das Papier beweist, dass man alle Zutaten (Apfel, Birne, Traube) prüfen muss, um zu wissen, ob die Explosion droht. Man kann nicht einfach raten oder Teile überspringen. Diese Erkenntnis setzt eine untere Grenze für die Rechenzeit: Man muss alle Teile prüfen, aber man muss nicht den ganzen Rest des Universums prüfen.

Zusammenfassung für den Alltag

Stellen Sie sich vor, Sie leiten eine große Firma.

Früher: Jedes Mal, wenn ein neuer Mitarbeiter eingestellt wurde, mussten Sie alle 10.000 Sicherheitsregeln der Firma von Hand durchgehen, um zu prüfen, ob jemand jetzt Zugriff auf das Bankkonto bekommt. Das dauerte Tage.
Jetzt (dank diesem Papier): Sie nutzen ein intelligentes System, das nur die wenigen Regeln prüft, die den neuen Mitarbeiter betreffen. Die Antwort kommt in Sekunden. Zudem kann das System sofort einen detaillierten Bericht erstellen: „Mitarbeiter X hat Zugriff, weil er mit Mitarbeiter Y und Z zusammenarbeitet."

Das Fazit:
Dieses Papier ist keine neue Erfindung, sondern eine Übersetzung. Es nimmt ein kompliziertes, neues Sicherheitsproblem und zeigt: „Hey, das ist eigentlich nur ein altes, bekanntes Logik-Problem." Dadurch erhalten wir sofort Zugang zu 30 Jahren an fortschrittlichen Algorithmen, die das Problem nicht nur lösen, sondern es massiv beschleunigen und transparenter machen. Es ist der Schlüssel, um KI-Agenten in der realen Welt sicher und effizient zu überwachen.

Each language version is independently generated for its own context, not a direct translation.

1. Problemstellung

Die Sicherheit von Multi-Agenten-KI-Systemen wird als computergestütztes Problem formuliert: Gegeben eine Menge von Fähigkeiten (Capabilities), die Agenten besitzen, und eine Menge verbotener Zustände, muss bestimmt werden, welche Zustände kollektiv erreichbar sind.

Das vorherige Framework von Spera [2026] nutzte Capability-Hypergraphen, um diese Erreichbarkeit zu modellieren. Dieses Framework hatte jedoch zwei wesentliche strukturelle und algorithmische Einschränkungen:

Fehlende inkrementelle Wartung: Jede Änderung im Hypergraphen (Hinzufügen/Entfernen einer Fähigkeit oder Regel) erforderte eine vollständige Neuberechnung der sicheren Audit-Oberfläche ($GF(A)$) von Grund auf. Dies führte zu hohen Kosten von $O(|V| \cdot (n + mk))$ .
Fehlende Entscheidungsprozedur für Inklusion: Es gab keinen effizienten Algorithmus, um zu entscheiden, ob die sichere Audit-Oberfläche einer Konfiguration $A$ in der einer anderen Konfiguration $A'$ enthalten ist ( $GF(A) \subseteq GF(A')$ ).
Komplexität der Nicht-Kompositionalität: Die Nicht-Kompositionalität von Sicherheit (d.h., dass zwei sichere Teilmengen in ihrer Vereinigung unsicher sein können) wurde zwar bewiesen, aber ohne tiefere strukturelle Erklärung im Rahmen der Logik.

2. Methodik und Kernidee

Die zentrale These des Papers ist, dass Capability-Sicherheit exakt der Auswertung in propositionaler Datalog ( $Datalog_{prop}$ ) entspricht.

Die Äquivalenz: Der Autor beweist eine formale, zweiseitige Äquivalenz zwischen Capability-Hypergraphen und $Datalog_{prop}$ $D a t a l o g_{p r o p}$ -Programmen (dem monadischen, bodenständigen, funktionenfreien Fragment der Prädikatenlogik).
- Jede Fähigkeit $v$ wird zu einem atomaren Prädikat $has(v)$.
- Jede Hyperkante (Regel) $(S, \{v\})$ , die feuert, wenn alle Elemente in $S$ vorhanden sind, wird zu einer Horn-Klausel: $has(s_1) \land \dots \land has(s_k) \Rightarrow has(v)$ .
- Die Sicherheitsbedingung wird durch eine stratifizierte Negation modelliert (z.B. $has(f) \Rightarrow forbidden$ ).
Formale Einbettung: Es werden explizite Polynomzeit-Isomorphismen in beide Richtungen konstruiert, die die Abschlussoperation (Closure), die Sicherheit und die Struktur der minimalen unsicheren Mengen ( $B(F)$ ) exakt erhalten.
Abgrenzung: Es wird bewiesen, dass diese Äquivalenz „tight" (eng) ist: Capability-Hypergraphen können genau die Klasse der monotonen booleschen Abfragen ausdrücken, aber keine nicht-monotonen Abfragen (wie Paritätsprüfungen oder Zählungen).

3. Wichtige Beiträge

A. Algorithmische Konsequenzen: Der „Locality Gap"

Durch die Identifikation von $GF(A)$ als Datalog-Sicht (View) wird die Theorie der inkrementellen Sichtwartung (Incremental View Maintenance) auf das Sicherheitsproblem angewendet.

DRed-Algorithmus: Statt einer Neuberechnung kann der DRed-Algorithmus (Delete and Re-derive) verwendet werden.
Komplexitätsverbesserung:
- Naive Neuberechnung: $O(|V| \cdot (n + mk))$ .
- Inkrementelle Wartung (DRed): $O(|\Delta| \cdot (n + mk))$ , wobei $|\Delta|$ die Anzahl der direkt betroffenen abgeleiteten Atome ist.
Locality Gap Theorem: Es wird ein asymptotischer Lückenbeweis ( $\Omega(n)$ ) geliefert. Für eine explizite Familie von Hypergraphen ist die inkrementelle Wartung um einen Faktor $n$ schneller als die Neuberechnung.
AND-Inspection Lower Bound: Es wird gezeigt, dass jeder korrekte Algorithmus, der die Aktivierung einer Regel mit $k$ Prämissen verifiziert, im Worst-Case alle $k+1$ Atome (die $k$ Prämissen plus das Ziel) inspizieren muss. Dies folgt aus der Struktur der AND-Bedingungen und wird über ein Orakel-Modell und das Yao'sche Minimax-Prinzip bewiesen.

B. Strukturelle und Semantische Konsequenzen

Entscheidbarkeit der Inklusion: Die Frage, ob $GF(A) \subseteq GF(A')$ , reduziert sich auf das Problem der Query Containment in $Datalog_{prop}$ . Da dies für propositionale Programme in Polynomialzeit entscheidbar ist, erhält man erstmals einen effizienten Entscheidungsmechanismus für Audit-Oberflächen-Inklusion.
Nicht-Kompositionalität als logisches Theorem: Die Nicht-Kompositionalität von Sicherheit wird als direkte Konsequenz der Semantik von Horn-Klauseln (AND-Regeln) in Datalog erklärt. Zwei sichere Datenmengen können unsicher werden, wenn ihre Vereinigung eine Regel aktiviert, die in den Teilmengen nicht feuerte. Dies ist eine strukturelle Eigenschaft des Systems, kein pathologischer Einzelfall.
Provenance Semirings: Die Ableitungszertifikate (Warum ist eine Fähigkeit erreichbar?) entsprechen exakt den Why-Provenance-Witnesses aus der Datenbanktheorie (Green et al., 2007). Dies ermöglicht eine algebraische Struktur (kommutativer Halbring) für die Kompression, Zusammensetzung und einheitliche Validierung von Sicherheitszertifikaten.

C. Transfer offener Probleme

Das Paper zeigt, dass jedes offene Problem aus der vorherigen Arbeit (Spera [2026]) auf ein bekanntes Problem in der Datalog-Theorie abbildbar ist:

PAC-Lernschranken $\rightarrow$ VC-Dimension von Datalog-Hypothesenklassen.
Probabilistische Sicherheit $\rightarrow$ Probabilistisches Datalog mit abhängigen Tupeln.
Adversarielle Robustheit (MinUnsafeAdd) $\rightarrow$ Sicht-Update-Probleme (View Update).

4. Ergebnisse und Evidenz

Theoretische Beweise: Die Äquivalenztheoreme (Encoding Theorem, Tight Expressivity Theorem) und die Komplexitätsresultate (Locality Gap, Lower Bounds) sind mathematisch streng bewiesen.
Empirische Validierung: Die Ergebnisse wurden auf einem Datensatz von 900 Agenten-Sessionen (Telco-Deployment) getestet.
- 42,6 % der Sessions erforderten konjunktive Ableitungen (AND-Regeln).
- 38,2 % der konjunktiven Sessions zeigten AND-Verletzungen (Nicht-Kompositionalität) unter einem Workflow-Planer.
- Ein auf Datalog basierter Planer zeigte 0% Verletzungen, was die theoretische Korrektheit der Äquivalenz empirisch untermauert.
- Die Ableitungstiefen und Statistiken stimmen mit den Datalog-Modellen überein.

5. Bedeutung und Fazit

Dieses Paper stellt einen Paradigmenwechsel in der Forschung zur KI-Sicherheit dar:

Keine neue Theorie nötig: Capability-Sicherheit benötigt keine neue, ad-hoc entwickelte Berechnungstheorie. Sie kann vollständig innerhalb des etablierten, gut verstandenen Rahmens der Datalog-Logik analysiert werden.
Zugang zu 30 Jahren Forschung: Durch die Äquivalenz erhält die KI-Sicherheitsforschung direkten Zugriff auf drei Jahrzehnte an Ergebnissen aus der Datenbanktheorie (Algorithmen, Komplexitätsklassen, offene Probleme).
Praktische Effizienz: Die Einführung von inkrementellen Wartungsalgorithmen (DRed) und Optimierungen (Magic Sets) bietet sofortige, nachweisbare Leistungsverbesserungen für dynamische Agentensysteme.
Fundamentale Einsicht: Die Arbeit klärt die Grenzen der Ausdruckskraft (nur monotone Logik) und liefert tiefe Erklärungen für Phänomene wie Nicht-Kompositionalität und die Komplexität von Sicherheitszertifikaten.

Zusammenfassend beweist das Paper, dass Capability-Sicherheit nicht nur ähnlich Datalog ist, sondern exakt Datalog ist, und nutzt diese Erkenntnis, um fundamentale algorithmische und strukturelle Lücken im vorherigen Framework zu schließen.