Repository navigation
Expand file tree
/
Copy pathlifecycle_probe.py
More file actions
183 lines (177 loc) · 6.77 KB
/
Copy pathlifecycle_probe.py
File metadata and controls
183 lines (177 loc) · 6.77 KB
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
"""Bounded independent exploration of a declared finite resource/state design.
Transition deltas and states are MODEL CLAIMS,not observed implementation facts.
Missing transitions are unknown,never implicitly treated as safe no-ops.
"""
from collections import deque
import re
def check(arguments, required_events=None):
if (
not isinstance(arguments, dict)
or set(arguments) - {"initial", "initial_units", "terminals", "transitions", "depth"}
or not {"initial", "terminals", "transitions"} <= set(arguments)
):
raise ValueError(
"lifecycle design requires initial,terminals,transitions and optional initial_units,depth"
)
def name(value):
if not isinstance(value, str) or not re.fullmatch("[A-Za-z][A-Za-z0-9_]{0,31}", value):
raise ValueError("bounded state/event identifier required")
return value
initial = name(arguments["initial"])
terminals = arguments["terminals"]
transitions = arguments["transitions"]
depth = arguments.get("depth", 6)
if not isinstance(terminals, list) or not 1 <= len(terminals) <= 16:
raise ValueError("1..16 unique terminal states required")
checked = [name(v) for v in terminals]
if len(set(checked)) != len(checked):
raise ValueError("unique terminal states required")
terminals = set(checked)
initial_units = arguments.get("initial_units", 0)
if type(initial_units) is not int or not 0 <= initial_units <= 8:
raise ValueError("initial_units must be integer in[0,8]")
if (
not isinstance(transitions, list)
or not 1 <= len(transitions) <= 64
or type(depth) is not int
or not 1 <= depth <= 12
):
raise ValueError("1..64 transitions and depth1..12 required")
outgoing = {}
states = {initial, *terminals}
seen_edges = set()
for item in transitions:
if not isinstance(item, dict) or set(item) != {"from", "event", "to", "delta"}:
raise ValueError("transition needs from,event,to,delta")
source, event, target = name(item["from"]), name(item["event"]), name(item["to"])
delta = item["delta"]
if type(delta) is not int or not -8 <= delta <= 8:
raise ValueError("resource delta must be integer in[-8,8]")
key = (source, event)
if key in seen_edges:
raise ValueError("deterministic finite design needs one transition per state/event")
seen_edges.add(key)
states.update((source, target))
outgoing.setdefault(source, []).append(dict(item))
if len(states) > 16:
raise ValueError("at most16 states supported")
required_events = required_events or {}
if (
not isinstance(required_events, dict)
or len(required_events) > 16
or any(not isinstance(v, list) or len(v) > 32 for v in required_events.values())
):
raise ValueError("caller required_events must map states to bounded event lists")
for state, events in required_events.items():
name(state)
[name(v) for v in events]
base = dict(
status="bounded_design_checked",
scope="declared resource model only;not code execution or concurrency proof",
max_depth=depth,
initial_units=initial_units,
limitations=[
"Initial units and transition deltas are design assumptions;implementation must be independently instrumented/tested.",
"Only declared transitions are explored;missing events are unknown,no implicit no-op. Interleavings beyond the explicit model and depth are unverified.",
],
)
queue = deque([(initial, initial_units, [])])
seen = set()
terminal_states = set()
reached = set()
missing = {}
cutoff = False
explored = 0
while queue:
state, held, path = queue.popleft()
key = (state, held, len(path))
if key in seen:
continue
seen.add(key)
reached.add(state)
explored += 1
if explored > 4096:
return dict(
base,
status="inconclusive",
reason="state budget exceeded;no partial pass",
explored=explored,
)
if held < 0:
return dict(
base,
status="counterexample",
counterexample=dict(
kind="release_without_ownership", state=state, held=held, events=path
),
explored=explored,
)
if state in terminals:
terminal_states.add(state)
if held:
return dict(
base,
status="counterexample",
counterexample=dict(
kind="terminal_resource_leak", state=state, held=held, events=path
),
explored=explored,
)
available = {r["event"] for r in outgoing.get(state, [])}
absent = set(required_events.get(state, [])) - available
if absent:
missing[state] = sorted(absent)
if len(path) == depth:
if outgoing.get(state):
cutoff = True
continue
for item in outgoing.get(state, []):
queue.append((item["to"], held + item["delta"], path + [item["event"]]))
if len(queue) > 8192:
return dict(
base,
status="inconclusive",
reason="pending-state budget exceeded;no partial pass",
explored=explored,
)
unknown = set(required_events) - reached
if unknown:
return dict(
base,
status="inconclusive",
reason="caller-required states not reached",
unreached_required_states=sorted(unknown),
explored=explored,
)
if missing:
return dict(
base,
status="inconclusive",
reason="caller-required events lack explicit transitions",
missing_events=missing,
explored=explored,
)
if not terminal_states:
return dict(
base,
status="inconclusive",
reason="no terminal reached within bound",
explored=explored,
)
unreachable = terminals - terminal_states
if unreachable:
return dict(
base,
status="inconclusive",
reason="some declared terminal paths untested",
unreached_terminals=sorted(unreachable),
explored=explored,
)
return dict(
base,
explored=explored,
terminal_states_checked=sorted(terminal_states),
reachable_states=sorted(reached),
depth_cutoff=cutoff,
complete_implementation_coverage=False,
)