Attacker

Attack search

An attack is a chain of at most k edits. The search space is a tree, harm over it is not submodular, and Aegis searches it with a bandit at every node.

Operators and units

Attackers use primitives in units: a removal; a rewire (remove A ⊑ B, inject A ⊑ B'); a flood (inject look-alikes such as Metall and attach them). candidate_units builds removal and rewire units over the elements with the largest impact, and flood units with flood=n; rewires that would close a cycle are left out.

Feasible chains

A chain is feasible under budget k when each action applies in the state the earlier ones left, its cost is at most k, it changes at least one triple, and its harm is positive. Problem 1 is to find the feasible chain of largest harm. The cheapest chain whose harm reaches a threshold gives a workload's robustness radius: the fewest edits that make the agent answer wrongly.

What the attacker knows

In every case the scarce resource is harm evaluations, so Aegis compares searches at equal evaluation counts. Every search returns a ScoredChain with its harm and evaluations; states are cached by digest, so two orders that reach the same state cost one evaluation.

Why greedy is not enough

The look-alike Metall does no harm alone, and the triple that attaches it cannot be added before it exists. Together they put a wrong class into an answer. Harm is therefore not submodular, greedy selection has no approximation guarantee, and greedy stops as soon as no single next unit raises harm.

UCT: a bandit at every node

The root of the tree is the honest ontology; a node's children are the units that apply and fit the budget. uct treats the choice of the next unit as a multi-armed bandit and repeats four steps until its evaluation budget is spent:

1. Select. Descend by UCB1: the child maximizing mean reward + c·√(ln N / n), skipping exhausted subtrees.
2. Expand. Open the next untried unit in impact order. Progressive widening allows at most ⌈N^0.5⌉ children for a node visited N times, so the search goes deep along the best-ranked units before it widens.
3. Roll out. Finish the chain with random units and score it.
4. Back up. Add the largest harm on the path (the attacker may stop at any prefix) to every node on it.

UCT is anytime (it returns the best chain so far) and complete (with enough evaluations it expands every chain and returns the optimum).

from aegis import beam, candidate_units, greedy, harm_over, random_chains, uct

harm = harm_over(scorer_for, questions)
units = candidate_units(onto, concept_deltas, relation_deltas, top=8)
best = beam(harm, onto, units, budget=3, width=3, k=1)[0]
found = uct(harm, onto, units, budget=3, evaluations=best.evaluations)   # same cost as beam
print(found.harm, [str(a) for a in found.chain])