File size: 13,270 Bytes
450ac2f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 | """Bounded robust policies over public adapter beliefs, with a separate checker.
The tree is contingent on raw observations, never private fixture state. Guarantees
are conditional on the real system being represented by the initial belief.
"""
from __future__ import annotations
from .core import CandidateSpace, _integer
from .identity import canonical_hash
from .interfaces import InterfaceError
def _cancelled(cancel):
if cancel and cancel():
# Local import avoids a study/adaptive import cycle.
from .study import Cancelled
raise Cancelled('Adaptive policy computation cancelled')
def synthesize_policy(space: CandidateSpace, ids, node_limit=20000, cancel=None) -> dict:
"""Find a minimum worst-case-depth tree, then lexicographic actions.
Iterative deepening searches an OR over actions and an AND over all response
partitions. A hard node cap returns SEARCH_LIMIT, never a negative proof.
All actions, including diagnostic ones, count toward the contract horizon.
"""
ids = space._ids(ids)
_integer(node_limit, 'node_limit', 1, 1000000)
expanded = 0
class Limit(Exception):
pass
def search(belief, prefix, remaining):
nonlocal expanded
_cancelled(cancel)
if expanded >= node_limit:
raise Limit
expanded += 1
if prefix and all(space.contract.accepts(space.semantic(i, prefix)) for i in belief):
return {'stop': True}
if not remaining:
return None
for action in range(space.machine.inputs):
word = prefix + (action,)
if not space.probe_is_safe(belief, word):
continue
partitions = {}
for i in belief:
partitions.setdefault(space.predict(i, word)[-1], []).append(i)
branches = {}
for raw, members in sorted(partitions.items()):
child = search(tuple(members), word, remaining - 1)
if child is None:
break
branches[str(raw)] = child
else:
return {'action': action, 'branches': branches}
return None
tree, complete = None, True
if ids:
try:
for depth in range(1, space.contract.horizon + 1):
tree = search(ids, (), depth)
if tree is not None:
break
except Limit:
complete = False
certificate = verify_policy(space, ids, tree) if tree is not None else None
if tree is not None and not certificate['valid']:
raise RuntimeError('Synthesized policy failed independent model checking')
return {'status': 'ADAPTIVE_ADMISSIBLE' if tree is not None else
'FAMILY_CONTRADICTED' if not ids else 'UNRESOLVED' if complete else 'SEARCH_LIMIT',
'admitted': tree is not None, 'word': None, 'policy': tree,
'candidate_count': len(ids), 'certificate': certificate,
'search': {'expanded_nodes': expanded, 'node_limit': node_limit,
'complete': complete, 'horizon': space.contract.horizon}}
def verify_policy(space: CandidateSpace, ids, policy) -> dict:
"""Check a supplied tree without calling the synthesizer.
Derive every branch belief anew from predictions; never trust stored survivor
counts, hashes, claimed leaf goals, or search metadata. This checks a finite
public model, not truth of its assumptions or real-world semantic grounding.
"""
ids = space._ids(ids)
checked, leaves, worst = 0, 0, 0
def visit(node, belief, prefix):
nonlocal checked, leaves, worst
checked += 1
if not belief:
raise ValueError('An empty belief cannot certify a policy')
if not isinstance(node, dict):
raise ValueError('Policy nodes must be objects')
if len(prefix) > space.contract.horizon:
raise ValueError('Policy exceeds the contract horizon')
if set(node) == {'stop'} and node['stop'] is True:
if not prefix or not all(space.contract.accepts(space.semantic(i, prefix)) for i in belief):
raise ValueError('Stop leaf does not satisfy every surviving interpretation')
leaves += 1
worst = max(worst, len(prefix))
return
if set(node) != {'action', 'branches'} or len(prefix) >= space.contract.horizon:
raise ValueError('Malformed action node or horizon exhausted')
action = _integer(node['action'], 'policy action', maximum=space.machine.inputs - 1)
branches = node['branches']
if not isinstance(branches, dict):
raise ValueError('Branches must be an object keyed by raw output')
word = prefix + (action,)
expected = {}
for i in belief:
if space.contract.hazard in space.semantic(i, word):
raise ValueError('An action risks a hazard under a surviving interpretation')
expected.setdefault(str(space.predict(i, word)[-1]), []).append(i)
if set(branches) != set(expected):
raise ValueError('Branches must cover exactly every possible raw output')
for raw, members in sorted(expected.items()):
visit(branches[raw], tuple(members), word)
try:
visit(policy, ids, ())
except (ValueError, TypeError, RecursionError) as exc:
return {'valid': False, 'reason': str(exc), 'checked_nodes': checked}
return {'schema': 'crosswire-policy-certificate-v1', 'valid': True,
'checked_nodes': checked, 'leaves': leaves, 'worst_case_steps': worst,
'candidate_count': len(ids),
'binding_hash': canonical_hash({'reference': space.machine.to_dict(),
'contract': space.contract.to_dict(),
'adapters': [space.adapters[i].to_dict() for i in ids],
'policy': policy}),
'scope': 'All branches in the declared finite candidate family; conditional on target inclusion, '
'stationarity, deterministic reset and truthful anchors. Not semantic grounding.'}
def policy_metrics(space: CandidateSpace, ids, policy) -> dict:
"""Compute structural and information-theoretic properties of a certified contingent policy tree."""
import math
ids = space._ids(ids)
cert = verify_policy(space, ids, policy)
if not cert['valid']:
return {'valid': False, 'reason': cert['reason']}
def count_nodes(node):
if not isinstance(node, dict) or 'stop' in node:
return 0, 0
branches = node.get('branches', {})
ins, mb = 1, len(branches)
for child in branches.values():
ci, cmb = count_nodes(child)
ins += ci
mb = max(mb, cmb)
return ins, mb
internal_nodes, max_branching = count_nodes(policy)
depths = []
# Equal action words can reach distinct leaves after different observations.
leaf_buckets = {}
for aid in ids:
node, word, path = policy, (), ()
while 'action' in node:
word += (node['action'],)
out = str(space.predict(aid, word)[-1])
path += ((node['action'], out),)
node = node['branches'][out]
depths.append(len(word))
leaf_buckets[path] = leaf_buckets.get(path, 0) + 1
n = len(ids)
leaf_sizes = sorted(leaf_buckets.values(), reverse=True)
info_gain = -sum((c / n) * math.log2(c / n) for c in leaf_sizes) if n else 0.0
return {
'valid': True,
'candidate_count': n,
'internal_nodes': internal_nodes,
'leaf_count': cert['leaves'],
'best_case_steps': min(depths) if depths else 0,
'worst_case_steps': cert['worst_case_steps'],
'expected_steps': round(sum(depths) / n, 6) if n else 0.0,
'max_branching_factor': max_branching,
'leaf_belief_sizes': leaf_sizes,
'information_gain_bits': round(info_gain, 6),
}
def execute_policy(target, policy, space: CandidateSpace, ids, cancel=None, fault_schedule=None, mode='adaptive', recovery_strategy='stabilize') -> dict:
"""Verify before reset, then execute only certified observation branches."""
if mode not in ('adaptive', 'shielded', 'recovery'):
raise ValueError('Unsupported adaptive execution mode')
if hasattr(target, 'set_phase'):
target.set_phase('deployment')
ids = space._ids(ids)
certificate = verify_policy(space, ids, policy)
if not certificate['valid']:
raise ValueError('Refusing uncertified policy: ' + certificate['reason'])
cp_step = fault_schedule.get('step') if fault_schedule else None
cp_type = fault_schedule.get('type') if fault_schedule else None
cp_detected = False
cp_det_step = None
cp_det_latency = None
def _check_cp(step_idx):
nonlocal cp_detected, cp_det_step, cp_det_latency
if (fault_schedule and fault_schedule.get('phase', 'deployment') in ('deployment', 'always')
and cp_step is not None and step_idx >= cp_step and not cp_detected):
cp_detected = True
cp_det_step = step_idx
cp_det_latency = step_idx - cp_step
deployment = {'word': None, 'executed_word': [], 'outputs': [], 'complete': False,
'mode': 'adaptive' if mode in ('adaptive', 'shielded') else 'recovery',
'shield_status': 'ACTIVE', 'intervened': False,
'hazard_averted': False, 'reasons': [], 'survivor_history': [len(ids)],
'target_steps': 0, 'resets': 0, 'target_calls': 0, 'error': None,
'certificate': certificate}
before = dict(target.counts)
node, active = policy, ids
try:
_cancelled(cancel)
target.reset()
while 'action' in node:
_cancelled(cancel)
action = node['action']
word = tuple(deployment['executed_word']) + (action,)
if not active or not space.probe_is_safe(active, word):
_check_cp(len(deployment['executed_word']))
deployment.update(intervened=True, shield_status='INTERVENED_MODEL_RISK')
deployment['reasons'].append('No unanimously safe continuation')
break
raw = target.step(action)
deployment['executed_word'].append(action)
deployment['outputs'].append(raw)
active = tuple(i for i in active if space.predict(i, word) == tuple(deployment['outputs']))
deployment['survivor_history'].append(len(active))
if not active or str(raw) not in node['branches']:
_check_cp(len(deployment['executed_word']) - 1)
deployment.update(intervened=True, shield_status='INTERVENED_ANOMALY')
deployment['reasons'].append('Observed response has no certified continuation')
break
node = node['branches'][str(raw)]
else:
deployment.update(complete=True, shield_status='COMPLETED')
if deployment['intervened'] and mode == 'recovery':
from .shield import RuntimeShield
shield = RuntimeShield(space, ids, space.contract, mode='recovery', cancel=cancel,
fault_schedule=fault_schedule, recovery_strategy=recovery_strategy)
shield.history_words = list(deployment['executed_word'])
shield.history_outputs = list(deployment['outputs'])
shield.active_survivors = active
shield.survivor_counts = list(deployment['survivor_history'])
shield.status = deployment['shield_status']
shield.intervened = True
shield.recover(target)
deployment['executed_word'] = list(shield.history_words)
deployment['outputs'] = list(shield.history_outputs)
deployment['survivor_history'] = list(shield.survivor_counts)
deployment['shield_status'] = shield.status
deployment['reasons'].extend(shield.reasons)
deployment['recovery'] = shield.recovery_record()
except InterfaceError as exc:
deployment['error'] = {'code': exc.code, 'message': str(exc)}
deployment['shield_status'] = 'INTERFACE_ERROR'
finally:
deployment.update(target_steps=target.counts['step_attempts'] - before['step_attempts'],
resets=target.counts['reset_attempts'] - before['reset_attempts'],
target_calls=target.counts['target_calls'] - before['target_calls'],
change_point={'scheduled': fault_schedule is not None, 'step': cp_step,
'type': cp_type, 'detected': cp_detected,
'detection_step': cp_det_step, 'detection_latency': cp_det_latency})
return deployment
|