使用令牌效率进行密钥扫描：罕见而非随机

# 稀有而非随机 来源：https://lookingatcomputer.substack.com/p/rare-not-random 在Regex（正则表达式）几乎就是全部（https://lookingatcomputer.substack.com/p/regex-is-almost-all-you-need）一文中，我们了解到结合使用正则表达式模式、熵值和基于规则的过滤器是检测候选机密信息的有效方法。正则表达式用于撒大网识别候选对象。熵值作为筛选捕获候选对象的主要过滤器，最后再应用额外的过滤器，例如检查常见英文单词的存在，或过滤已知“安全”文件如go\.sum。熵值在过滤假阳性方面做得不错，但仍有很大改进空间，尤其是在评估通用机密时。是否有比熵更好的东西能作为正则捕获后的主过滤器？本文探讨字节对编码（Byte-Pair Encoding）是否可以作为机密扫描中比熵更有效的替代方案。 [插图链接](https://substackcdn.com/image/fetch/$s_!_0mR!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fd8c797f8-662c-4c0c-a391-7c6a49861eed_1440x1157.jpeg) 稀有的*——四叶草 我要感谢GitHub用户"DmitriyAlergant (https://github.com/gitleaks/gitleaks/issues/1924)"在Gitleaks仓库的issue中提交了这个想法。 熵到底是什么？据约翰·冯·诺依曼与克劳德·香农交谈时所说，“没人真正知道 (https://mathoverflow.net/questions/403036/john-von-neumanns-remark-on-entropy)”，但维基百科知道。香农熵衡量字符串的平均不可预测性，即每个字符携带的信息量。当字符均匀分布时（许多不同字符，无明显模式），每个字符更难预测，因此熵值高。当少数字符占主导地位时，下一个字符容易猜测，因此熵值低。在实践中，这意味着像`aaaaaa111111`这样的字符串得分低，而像`xA9fP2qL0sRw`这样的字符串得分高。就机密检测而言，这使得熵成为识别“看起来随机”字符串（候选机密）的合理初筛。 但我们真的想把随机性作为机密检测的主要过滤器吗？原谅这里套用了“不是X，而是Y”的LLM常见说法——机密不仅仅是随机的，它们与人类书写的自然语言分布相比在统计上是不寻常的。更直白地说，机密是稀有的。一个base64编码的字符串、一个UUID、一个真正的机密和一个看起来奇怪的依赖字符串可能有相似的熵值，尽管它们在现实世界中出现的频率本质上不同。熵无法区分“这看起来随机”和“这在英语文本或源代码中几乎从不出现”。与其用熵来衡量随机性，我们是否可以尝试衡量一个字符串是*非词汇表内*的还是*非自然语言*的。 那么我们如何检测一个字符串是看起来多么非自然语言或稀有呢？当然是使用字节对编码 (https://huggingface.co/learn/llm-course/en/chapter6/5) (BPE)！字节对编码分词器隐式地反映了其训练文本的频率分布。常见的单词和子词会被合并成长令牌，而稀有或不自然的字符串会被拆分成许多短令牌。 以下是使用cl100k\_base分词器1 (https://lookingatcomputer.substack.com/p/rare-not-random#footnote-1)的几个例子： - “Hello World” → \[15339, 1917\] - “lookingatcomputer” → \[20986, 266, 44211\] - “kj2h3f2fuaafewa” → \[93797, 17, 71, 18, 69, 17, 69, 4381, 2642, 365, 64\] 因为BPE通过重复合并训练数据中最常见的字符对来构建其词汇表，所以它的分词自然反映了不同模式出现的频率。听起来是不是有点像我们试图衡量的稀有性？ 常见的英文单词有自己独立的令牌，因为它们在训练中频繁出现，例如，“password”是令牌 \[3918\]。“github”是令牌 \[5316\]。“function”是令牌 \[1723\]。但像`ghp_xK7mP9qL2wR5nT3vJ8fY`这样的随机API密钥呢？ [插图链接](https://substackcdn.com/image/fetch/$s_!I958!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F19520b57-b9f5-44cc-8f7f-5601bb7c0ac5_259x54.png) 分词器在训练时很可能从未见过这个特定序列，因此它将字符串拆分成更小的对，最终回退到单个字节，最终分词结果为 \[876, 79, 3292, 42, 22, 76, 47, 24, 80, 43, 17, 86, 49, 20, 77, 51, 18, 85, 41, 23, 69, 56\]。这是一个24个字符的字符串产生了22个令牌，这意味着分词器几乎没认出其中的任何东西。 查看https://tiktokenizer.vercel.app/?model=cl100k_base看看不同字符串是如何被分词的。 如果BPE分词器将稀有字符串拆分成许多短令牌，那么我们可以通过比较原始字符串长度与生成的令牌数量来衡量字符串有多稀有。让我们称之为**令牌效率（Token Efficiency）**。 `token_efficiency = len(string) / len(tokens)` 自然语言与分词器的词汇表映射良好，因此常见短语产生的令牌较少。类机密字符串则不然，因此它们产生许多令牌。 考虑我们的例子`ghp_xK7mP9qL2wR5nT3vJ8fY`。它的令牌效率为1.1（一个24字符的字符串产生了22个令牌）。像`Hello World`这样的短语效率为3.7（11个字符分成3个令牌）。如果机密持续产生较低的令牌效率分数，而日常文本产生较高的分数，那么令牌效率可以作为机密检测中有用的正则后过滤器。 为了测试这个想法，我们可以参考CredData (https://github.com/Samsung/CredData)数据集，它包含数千个从真实仓库中提取的、标记好的真机密和非机密样本。如果令牌效率确实能反映稀有性或“非日常语言性”，那么观察CredData数据集机密*值*的令牌效率分布，可能会揭示机密与非机密之间的差距。 CredData数据集分为索引文件和数据文件。索引文件存储你需要的元数据，如标签、行和列范围以及文件名。它们不包含实际的机密值，因此你必须通过在指定范围切割源文件来重构每个机密。这就是我采取的方法。我直接从数据集中提取了每个标记的机密值。这意味着我们评估的不是令牌效率本身能否*检测*机密。相反，我们评估的是令牌效率能否*分类*已捕获的候选机密，这使其成为正则表达式后的过滤步骤，而非独立检测器。 你可以在这里 (https://github.com/zricethezav/creddata_helpers/blob/main/charts.py)查看生成这些图表的代码： [插图链接](https://substackcdn.com/image/fetch/$s_!hzrL!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F4a38068d-afbf-41d7-af68-b855cc6fad9d_2048x1025.png) 看起来很有希望！2.5似乎是令牌效率的一个很好的最小阈值。Gitleaks对通用机密使用3.5的熵阈值。 使用这些阈值，让我们看看分类结果。 [插图链接](https://substackcdn.com/image/fetch/$s_!8n7e!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F561d8a42-3a37-4c87-baba-93263053d892_3511x1758.png) ``` Token Efficiency: Precision=57.3% Recall=98.6% F1=0.725 Entropy: Precision=21.1% Recall=70.4% F1=0.325 ``` 98.6%的召回率相当不错。我们正确分类了几乎所有的真机密，只留下了149个假阴性。令牌效率的假阳性数量不少，但这和熵的差别简直是天壤之别。熵产生了28,000个假阳性（几乎是令牌效率的4倍）和3,000个假阴性。加入一个简单的单词过滤器对两种方法都有帮助，但令牌效率在F1分数上仍然胜出。这个单词过滤器会忽略包含一个或多个出现超过一次的4个或更多字符单词的机密。 [插图链接](https://substackcdn.com/image/fetch/$s_!-btk!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fc9fadac4-f779-456b-810b-d9d76e561101_3511x1758.png) ``` TE + Word Filter: Precision=80.4% Recall=95.8% F1=0.874 Entropy + Words Filter: Precision=76.6% Recall=67.1% F1=0.715 ``` 这个过滤器为熵做了很多繁重的工作，但也帮助我们过滤了令牌效率的假阳性。对于令牌效率，应用这个过滤器后，假阳性从7894个降至2508个，同时只引入了308个新的假阴性，这显著提升了我们的F1分数。 如果你想重现这些结果，可以在这里查看一些代码：https://github.com/zricethezav/creddata_helpers。 让我们看看熵漏掉但令牌效率捕获到的一些机密。 **e2aa9ae57d893a1** 这个字符串的熵值为3.125。相当高，但未达到Gitleaks和其他一些机密检测器使用的3.5阈值。e2aa9ae57d893a1在cl100k\_base下产生 \[68, 17, 5418, 24, 6043, 3226, 67, 26088, 64, 717\] 的令牌，其令牌效率为1.6，远低于2.5的令牌效率阈值。 **mcjrx4** 这是一个密码，而且不是很好的密码。密码是熵过滤器的一个棘手类别，因为它们通常（不幸地）较短，而短字符串通常熵值较低。这个密码的熵值仅为2.58。但分词器将其分解为接近字节级的令牌 \[13183, 73, 12940, 19\]，令牌效率为1.5。六个字符，四个令牌。分词器没有将其识别为自然语言，而这正是我们想要的信号。 **U@kkf8fo\!\!** 另一个密码。这个密码很有趣，因为它包含特殊字符。机密检测，特别是针对通用机密和密码，挑战之一在于编写能捕获*大多数*机密的正则表达式。使用旨在捕获*大多数*机密的正则表达式的问题在于，它有可能让很多假阳性通过，比如电子邮件、URL等。因此，在你捕获组的字符类中定义的每个特殊字符如`@`或`\!`或`/`，都可能增加引入更多假阳性的机会。因此我们可以看到Gitleaks的通用捕获组非常严格：`[\w\.=\-]{10,150}`。使用令牌效率过滤器，我们可能可以放宽该模式以包含更多特殊字符。好的，考虑到这个背景，以下是该示例的熵和令牌效率比较。**U@kkf8fo\!\!** 的熵值为2.72，产生以下令牌 \[52, 31, 19747, 69, 23, 831, 51447\]，令牌效率为1.42（10个字符，7个令牌）。 关于密码的一点说明。令牌效率在分类*弱*密码（如“password123”或“chibearsfan123”）方面表现不佳。这些密码基本上就是自然语言，因此令牌效率值高。密码短语（Pass phrases）效果也不好，因为它们通常就是直接的单词。 对性能的影响可以忽略不计。在捕获的CredData机密上计算熵的平均时间为每个字符串4.55微秒，而计算令牌效率（使用cl100k\_base）需要11.75微秒2 (https://lookingatcomputer.substack.com/p/rare-not-random#footnote-2)。2.5倍的差异可能看起来很大，但你必须记住，就机密检测而言，瓶颈是正则表达式，而不是之后快速过滤器如熵或令牌效率。 CredData数据集的维护者们创建了一个令人印象深刻的机密扫描器CredSweeper (https://github.com/Samsung/CredSweeper)，它使用正则表达式、熵*和*RNN (https://credsweeper.readthedocs.io/en/latest/overall_architecture.html)来检测机密。在一个充斥着“LLM可以零假阳性检测机密”（学术界和工业界皆是3 (https://lookingatcomputer.substack.com/p/rare-not-random#footnote-3)）的世界里，看到三星的工程师们基于更“传统的机器学习”来构建机密检测器是令人耳目一新的。值得称赞。CredSweeper在针对CredData测试时，取得了令人印象深刻的**.85** F1分数。相当不错！让我们看看是否能在**Betterleaks (https://github.com/betterleaks/betterleaks)**中使用新的令牌效率过滤器超越它。 哦，对了。Betterleaks是什么？这是一个继承Gitleaks遗产的新项目。我会在另一篇文章中详细说明，但你需要知道的是，它是我维护的Gitleaks的直接替代品……而且它会更好……因为名字。 这个配置 (https://github.com/zricethezav/creddata_helpers/blob/main/configs/token_efficiency.toml)添加了几条新规则并对现有默认配置进行了一些小调整。使用此配置并在CredData数据集上运行Betterleaks，得到F1分数为**.892**。 ``` (Token Efficiency + (Low) Entropy on Generic Rule + Rule tweaks) Benchmark Results: ======================================== TP (True Positives): 10796 FP (False Positives): 1031 TN (True Negatives): 42572 FN (False Negatives): 1578 ---------------------------------------- Accuracy: 0.9534 Precision: 0.9128 Recall: 0.8725 F1 Score: 0.8922 ``` 相当不错。 [插图链接](https://substackcdn.com/image/fetch/$s_!7lXj!,f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fbf0f0786-a58a-477f-a66e-da44bd1fefea_504x281.avif) 仅*使用*令牌效率，我们得到： ``` (Just Token Efficiency + Rule tweaks) Benchmark Results: ======================================== TP (True Positives): 10843 FP (False Positives): 1722 TN (True Negatives): 41881 FN (False Negatives): 1531 ---------------------------------------- Accuracy: 0.9419 Precision: 0.8630 Recall: 0.8763 F1 Score: 0.8696 ``` 在使用令牌效率过滤器但不对通用规则设置低熵阈值的情况下，我们引入了约700个假阳性。尽管如此，即使没有该通用规则的熵过滤器，我们也得到了**.86**的F1分数，这并不差。 如果我们不使用令牌效率过滤器，而是仅依赖规则调整和熵，分数会怎样？ ``` (Just Entropy + Rule tweaks) Benchmark Results: ======================================== TP (True Positives): 8498 FP (False Positives): 1041 TN (True Negatives): 42562 FN (False Negatives): 3876 ---------------------------------------- Accuracy: 0.9122 Precision: 0.8909 Recall: 0.6868 F1 Score: 0.7756 ``` 好吧，所以 .892 对比 .776 是一个相当大的差距。仅使用熵过滤器比令牌效率过滤器多出超过2000个假阴性和80个假阳性。 你可以在这里 (https://github.com/betterleaks/betterleaks/blob/1ee7898e728f8612e39b97833c6caa9b4f5a8e41/detect/detect.go#L673-L698)查看令牌效率过滤器的代码。 ``` func (d *Detector) failsTokenEfficiencyFilter(secret string) bool { analyzed := secret if len(analyzed) < 20 && strings.ContainsAny(analyzed, "\n\r") { analyzed = newlineReplacer.Replace(analyzed) } tokens := d.tokenizer.Encode(analyzed, nil, nil) matches := words.HasMatchInList(analyzed, 5) if len(matches) > 0 { return true } threshold := 2.5 if len(analyzed) < 12 { threshold = 2.1 matches := words.HasMatchInList(analyzed, 3) if len(matches) == 0 { threshold = 2.5 } } return float64(len(analyzed))/float64(len(tokens)) >= threshold } ``` 该过滤器略