Linear credential matching and performance gates for user text
用户文本凭据识别的线性匹配与性能门禁
[ui-secret-mask](../../../../packages/client/ui-secret-mask/README.md) recognizes credentials in every sent user text. The UserText scheduler queries the matcher again after each accepted node, so a text costs the sum of all its queries. Most text contains no credential, so the first goal is that such text pays as little as possible; second, text with credentials pays in proportion to their number and length; adversa
English
Problem
ui-secret-mask recognizes credentials in every sent user text. The UserText scheduler queries the matcher again after each accepted node, so a text costs the sum of all its queries. Most text contains no credential, so the first goal is that such text pays as little as possible; second, text with credentials pays in proportion to their number and length; adversarial input must stay linear. Constraints: no regex backtracking, prefix pruning, linear total over all queries of one text, and no allocation before a node is returned.
Decision
Algorithm: what each part does and costs
| Part | Method | Cost over all queries of one text |
|---|---|---|
| Finding format starts | All starting literals (sk-, sk_live_ and kin, AIza, ghp_ and kin, github_pat_, glpat-, npm_, hf_, AKIA/ASIA, LTAI, AKID, xox?-, whsec_, eyJ, -----BEGIN , ://) form one literal-only alternation grouped by shared leading characters, scanned with test | Θ(n) native comparisons; no quantifier, so no backtracking; two adjacent queries reread at most one literal |
| Overlapping literals | Where a literal's suffix begins another literal (the - of sk-, glpat-, xox?- and -----BEGIN ), the scan resumes at that suffix; resume offsets are computed from the literal table at module load | At most one character back per hit |
| Identifying the hit | A table keyed by the hit's last two code units; only the three shared endings (t_, e_, IA) are told apart with startsWith | O(1) per hit |
| Format checks | Word boundaries, lengths, digit position, and the .eyJ separator are numeric comparisons; a private-key label reads at most 52 characters and a scheme at most 16 back; character runs are measured natively with sticky [class]* patterns, which stop at the first character outside the class and have nothing after them to backtrack into | O(1) per hit plus run measurement |
Runs, next digit, next END line | Each matcher instance memoizes per text in one Int32Array: four slots for [A-Za-z0-9_-] (a JWT uses three runs at once), one slot per other class, the next digit, and the next valid END line. These are facts of the text, reused across queries and cleared when a query names another text | Each character measured at most once per class |
| Address passwords | When the :// precedes the query offset and the password follows it, the matcher first confirms that :, a nonempty password, and @ follow the offset, and only then walks back over the user name; an offset inside :// is checked directly | At most 258 characters back, only where :password@ follows the offset |
| Joining candidates | Candidates are processed in start order; an address password starts after its :// and waits until the scan passes its start, and no other :// can occur before then because user names and passwords exclude /; overlapping candidates join the earliest and take its mask; a range that reaches the end of the text ends the scan | O(1) per candidate, no list |
| Masks | A range of prefixed formats only is ASCII without line breaks, so its mask is a slice of its first 8 characters plus a slice of a shared mark string; a private-key body skips ordinary characters natively and takes one slice of a shared "marks plus line break" string per line; address passwords and other mixed ranges count code points character by character | Θ(masked characters + lines), the order of the output |
Memory
- Nothing is allocated before a node is returned:
testcreates no match array, memo slots are a preallocated integer array, loops use indexes instead of iterators, and candidate ranges live in local numbers. - Each credential allocates only its result: the node, its
dataobject, and the mask. A one-line mask is the concatenation of two slices; a multi-line mask adds one slice and one concatenation per line. - Each instance keeps a reference to the last queried text until a query names another text.
Trade-offs
- Scanning is native, decisions are JavaScript: in V8 a per-character JavaScript loop is slower than a native literal scan or native run measurement, so all work proportional to input length (finding starts, measuring runs, skipping key bodies) uses non-backtracking native patterns, and JavaScript makes a constant number of decisions per hit.
- Pruning depends on the formats only: starts come from format literals, not from anchors chosen by character frequency in natural text, so text with any character distribution pays the same linear cost.
- Memo per text, not per query: a memo inside one query cannot stop later queries from measuring the same characters again; keyed by text and owned by the instance, cleared on a new text, it costs one retained string reference.
- Masks use shared-string slices: faster than writing into a buffer and decoding it; a multi-line mask allocates in proportion to its lines, which is part of the output.
Performance gate
benchmarks/user-text runs in the required node 24 / benchmarks lane. Its compiled worker uses the production UserText registry and every shipped matcher (session, file, folder, skill, command, whitespace, credential) under plain Node, in two processes: timing and allocation.
| Item | Content |
|---|---|
| Workloads | Without credentials: ordinary messages, and long prose, code, base64, Markdown, log, JSON, and shell text. With credentials: messages each carrying one kind (model key, GitHub token, cloud key ID, JWT, address password, private-key block), and batches of .env keys. Adversarial: repeated input shaped against each format's prefix, length, and separator rules, at two sizes. All generated from constants; credential samples are assembled at run time |
| Timing | Ten unmeasured pairs warm each workload with the same evaluation count as measured pairs. Five measured pairs alternate baseline-first and matcher-first order; each evaluation builds a fresh registry, document, and matcher instance and times evaluation only. A single-document sample averages twenty evaluations; a 5,000-message sample evaluates the batch once. Each side selects its minimum sample mean, with the mean process CPU time from that sample. The worker JSON in CI logs includes every measured pair and averaging count; the HTML report shows the selected with-credential mean. Registry disposal completes outside the timer before the next evaluation, preventing cleanup and retained registries from accumulating. Warm-up retains no matcher memo |
| Allocation | A separate process with --expose-gc and a fixed semi-space larger than any evaluation; after warm-up and GC, the matcher alone answers every query once and the young-generation growth is taken; GC event timestamps confirm no GC ran inside the interval |
| Assertions | Without credentials: absolute budgets and a cap on the with/without time ratio; with credentials: absolute budgets and the time ratio when the key count doubles; adversarial: absolute budgets and doubling ratios; allocation: a floor plus caps per credential, per line break inside masks, and per masked character |
| Excluded | Cold code compilation, React rendering, browser paint and layout; allocation results are asserted and printed to the console, not added to the HTML report |
Expectations come from an x64 development machine. CI time budgets are converted with the shared scale and headroom; ratios are not machine-scaled. Unmatched with/without ratios use a common 1.75× headroom because independently selected minima vary with V8 tiering and workload shape; unchanged-worker CI ratios reached 1.65× their reference expectations. Absolute time budgets, doubling ratios, and allocation budgets retain their existing limits. Negative controls: the same benchmark fails when pointed at the regular-expression implementation or at an implementation that rebuilds its memo per query. Equivalence tests compare this implementation with the regular-expression one (regex-oracle.client.ts) node by node through the production scheduler and from every query offset.
The reference constants are calibrated for minima of five single evaluations. Minimum-of-five sample means use the existing absolute headroom without recalibration. Averaging can move the ratio of independently selected minima in either direction; a threefold matcher-work negative control verifies that the JSON ratio limit still rejects extra scanning.
Alternatives considered
- Unwarmed, separate baseline and matcher batches: sub-millisecond baseline measurements can reach optimized code before the matcher’s newly exercised paths do, and separate batches amplify clock-speed drift. Per-workload warm-up, adjacent pairs, and fixed batches compare warmed code while limiting noise in short intervals and preserving fresh documents and matcher state.
- One quantified pattern per format, run from every query: patterns without a hit scan to the end of the text each time, so cost grows quadratically with credentials, and length quantifiers backtrack on failure.
- One large quantified pattern for all formats: one scan finds the leftmost match, but branch quantifiers still backtrack on failure.
- Scanning for rare characters first, then looking back for prefixes: faster on ordinary text, but cost depends on character distribution, and text dense in
-or_becomes clearly slower. - A pure JavaScript Aho–Corasick automaton: allocation-free, but per-character table lookups carry a state dependency and are slower than the native literal scan, so the most common text, without credentials, gets slower.
- A memo rebuilt per query: with accepted tokens between digit-free
sk-prefixes, every query's digit search reaches the end of the text, which grows quadratically. - Building private-key masks in one buffer with
TextDecoder: one string per block, but each decode's fixed cost exceeds shared-string slices. execfor hits andfor…ofover memo slots: they allocate match arrays and iterator results.
Consequences
- The added cost on text without credentials is one native scan plus checks at literals; it cannot drop further without depending on character distribution.
- A new format adds its literal and a forward-only check to the format table; resume offsets and the hit table are derived. The literal-pattern unit test rejects quantifiers, and the benchmark rejects superlinear scans and extra allocation.
- The plugin creates and owns the matcher instance in
apply; tests and the benchmark create one per sample and share no memo.
中文
问题
ui-secret-mask 在每条已发送用户文本上识别凭据。UserText 调度器在每个被采纳的节点之后再查询一次匹配器，一段文本的成本是它全部查询之和。大部分文本不含凭据，所以首要目标是让不含凭据的文本尽量少付成本；其次是含凭据文本的成本只与凭据个数和长度成正比；对抗输入必须保持线性。约束：正则不回溯；按前缀剪枝；一段文本的全部查询合计线性；返回节点之前不分配内存。
决定
算法：每部分的做法与复杂度
| 部分 | 做法 | 一段文本全部查询的代价 |
|---|---|---|
| 找格式起点 | 所有起始字面量（sk-、sk_live_ 等、AIza、ghp_ 等、github_pat_、glpat-、npm_、hf_、AKIA/ASIA、LTAI、AKID、xox?-、whsec_、eyJ、-----BEGIN 、://）按共同前缀分组成一个只含字面量的交替正则，用 test 扫描 | Θ(n) 次原生比较，没有量词因而不回溯；相邻两次查询至多重读一个字面量 |
| 重叠的字面量 | 字面量的后缀若是另一个字面量的开头（sk-、glpat-、xox?- 的 - 与 -----BEGIN ），扫描从该后缀处继续；续扫位置在模块加载时由字面量表算出 | 每个命中至多回退一个字符 |
| 识别命中的字面量 | 命中末尾两个码元查表；只有共享结尾的三组（t_、e_、IA）再用 startsWith 区分 | 每个命中 O(1) |
| 格式校验 | 单词边界、长度、数字位置、.eyJ 分隔用数值比较；私钥标签至多读 52 个字符，协议名至多回看 16 个字符；字符段用粘性 [字符类]* 原生测量，模式在第一个不属于该类的字符处停止，后面没有内容，不回溯 | 每个命中 O(1) 加字符段测量 |
字符段、下一个数字、下一行 END | 每个匹配器实例用一个 Int32Array 按文本记忆：[A-Za-z0-9_-] 四个槽（JWT 同时用三段），其余字符类各一个槽，另记下一个数字和下一行有效 END 的位置；这些是文本本身的事实，跨查询复用，查询换成另一段文本时清空 | 每类字符每个字符至多测量一次 |
| 地址密码 | :// 在查询起点之前、密码在起点之后时，先确认起点后面紧跟 :、非空密码和 @，才回看用户名找 ://；起点落在 :// 中间时直接检查 | 回看至多 258 个字符，且只在 :密码@ 紧跟起点时发生 |
| 合并候选 | 候选按起点顺序处理；地址密码在其 :// 之后开始，延后到扫描越过它的起点，此前不会出现另一个 ://（用户名和密码不含 /）；重叠的候选并入最早的候选并使用其遮挡方式；范围到文本末尾即停止扫描 | 每个候选 O(1)，不建列表 |
| 遮挡串 | 只由前缀格式组成的范围全是 ASCII 且没有换行，遮挡串是前 8 个字符的切片加一个共享星号串的切片；私钥正文用原生模式跳过普通字符，每行取一个"星号加换行"共享串的切片；地址密码和其他混合范围逐字符计数码点 | Θ(遮挡字符数 + 行数)，与输出同阶 |
内存
- 返回节点之前不分配：
test不产生匹配数组，记忆槽是预先分配的整数数组，遍历用下标而不是迭代器，候选范围存在局部数值里。 - 每个凭据只分配结果：节点、
data对象和遮挡串。单行凭据的遮挡串是两个切片的拼接；多行遮挡每行再加一个切片和一次拼接。 - 每个实例保留最近一次查询的文本引用，直到查询另一段文本。
取舍
- 扫描交给原生正则，判断交给 JavaScript：V8 中逐字符的 JavaScript 循环比原生字面量扫描和原生字符段测量慢；凡是与输入长度成正比的工作（找起点、量字符段、跳过私钥正文）都用不回溯的原生模式，JavaScript 只做每个命中常数次的判断。
- 只依赖格式本身的剪枝：起点由格式字面量决定，不按字符在自然文本中的频率挑锚点，因此任何字符分布的文本都付同样的线性成本。
- 记忆按文本而不按查询：一次查询内的记忆不能阻止后续查询重新测量同一段字符；以文本为键、由实例持有，换文本即清空，代价只是保留一个字符串引用。
- 遮挡串用共享串切片：比先写入缓冲区再整体解码更快；多行遮挡的分配与行数成正比，仍属于输出本身。
性能门禁
benchmarks/user-text 在 node 24 / benchmarks 必跑 lane 中运行。编译后的 worker 使用生产的 UserText 注册表和全部已发布匹配器（会话、文件、文件夹、skill、命令、空白、凭据），在纯 Node 下分两个进程运行：计时与分配。
| 项 | 内容 |
|---|---|
| 负载 | 无凭据：普通消息，以及散文、代码、base64、Markdown、日志、JSON、shell 长文本。含凭据：每条消息含一种凭据（模型密钥、GitHub 令牌、云密钥 ID、JWT、地址密码、私钥块），以及成批的 .env 密钥。对抗：针对每种格式的前缀、长度与分隔规则构造的重复输入，两种长度。全部由常量生成，凭据样本运行时拼接 |
| 计时 | 每个负载先用十组未计入结果的配对预热，每组的求值次数与测量配对相同。五组测量交替以基线或凭据匹配器开头；每次求值新建注册表、文档和匹配器实例，只计求值。单文档样本取二十次求值的平均值，5,000 条消息的样本则整批求值一次。两侧各取样本均值的最小值，并保留对应样本的平均进程 CPU 时间。CI 日志中的 worker JSON 包含全部测量配对和求平均值的次数，HTML 报告展示选中的带凭据匹配器均值。每次求值在计时结束后等待注册表清理完成，再开始下一次，避免清理工作和未释放注册表积累。预热不保留匹配器记忆 |
| 分配 | 单独进程，--expose-gc，semi-space 固定为大于任何一次求值的大小；预热后 GC，再单独驱动匹配器回答全部查询一遍，取新生代增量；用 GC 事件的时间戳确认区间内没有 GC |
| 断言 | 无凭据：绝对预算，以及"有/无凭据匹配器"的耗时比上限；含凭据：绝对预算，密钥数翻倍时的耗时比；对抗：绝对预算与翻倍耗时比；分配：底噪加每个凭据、每个遮挡内换行和每个遮挡字符的上限 |
| 排除 | 冷代码编译、React 渲染、浏览器绘制与布局；分配结果只用于断言并输出到控制台，不进 HTML 报告 |
预期值来自 x64 开发机。CI 时间预算按共享比例与余量换算；比值不随机器缩放。无凭据文本的有／无匹配器耗时比统一使用 1.75 倍余量，因为独立选取的最小值会随 V8 编译层级和文本形状变化；未改变的 worker 在 CI 中达到过参考预期的 1.65 倍。绝对耗时、翻倍比和分配预算保持原有上限。负对照：同一 benchmark 指向正则实现或"每次查询新建记忆"的实现时都会失败。等价性测试经生产调度器逐节点比较本实现与正则实现（regex-oracle.client.ts），并对每个查询起点单独比较。
参考常量按五次单独求值的最小值校准；五组样本均值的最小值使用既有绝对耗时余量，不重新校准。求平均值可能使两侧独立最小值的比值向任一方向变化；将匹配器工作量增至三倍的负对照验证 JSON 比值上限仍能拒绝额外扫描。
考虑过的替代方案
- 不预热、分批测量基线和匹配器：亚毫秒基线测量可能先进入优化后的代码，而匹配器新触及的路径还未完成优化；分批测量也会放大时钟频率漂移。逐负载预热、相邻配对和固定批次比较预热后的代码，降低短区间测量的噪声，同时保持文档和匹配器状态全新。
- 每次查询对每个格式各跑一个带量词的正则：没有命中的正则每次都扫到文末，凭据多时平方增长；长度量词在失败时回溯。
- 把全部格式合成一个带量词的大正则：一次扫描能找到最左匹配，但各分支的量词失败时仍回溯。
- 先找稀有字符再回看前缀：普通文本扫描更快，但成本取决于字符分布，
-、_密集的文本明显变慢。 - 纯 JavaScript 的 Aho–Corasick 自动机：可以零分配，但逐字符查表有状态依赖，比原生字面量扫描慢，最常见的无凭据文本反而变慢。
- 每次查询新建记忆：被接受的 token 之间夹着无数字的
sk-时，每次查询的数字查找都扫到文末，平方增长。 - 用
TextDecoder从缓冲区一次生成私钥遮挡串：每块只分配一个字符串，但每次解码的固定开销高于共享串切片。 - 用
exec取命中、用for…of遍历记忆槽：分别分配匹配数组和迭代器结果。
影响
- 无凭据文本的额外成本是一遍原生扫描加字面量处的校验；不依赖字符分布就无法再降。
- 新增格式要在格式表里加字面量和只向前的校验；续扫位置与命中识别表自动生成。字面量正则的单测拒绝量词，benchmark 拒绝超线性扫描和多余分配。
- 匹配器实例由插件在
apply中创建并持有；测试和 benchmark 每个样本新建实例，不共享记忆。