两个信息技术理论-信息安全篇-华盾信卫信息技术(浙江)有限公司

两个信息技术理论

2025-06-25

1.前言

自2003年起，我设计过很多算法和信息技术，主要集中在差分压缩、敏感数据识别、字符串匹配和数据传输等领域，但是，这些算法和技术都是针对具体问题单独研究出来的，比较零散，不成体系。从2013年开始，我开始系统性地梳理这些算法和技术，形成了两个理论框架：差分压缩理论、字符串近似匹配理论。

此文简要介绍两个理论的大概思想，以便于跟业界交流和合作。

2.差分压缩理论

我接触差分压缩问题是从设计手机固件的差分压缩优化算法开始的。2000年代初，硅谷的一家OTA企业在跟全球其它三家OTA产商在代表行业核心技术的差分压缩引擎领域一决高下，他们从美国东部邀请到我加盟以优化差分压缩算法。这项任务的难点是如何消除机器代码的次级变化 (secondary changes)。经过一个半月的研究，我给出了解决方案，其关键点在于建立机器代码变化理论。依据此理论，可以设计代码映射匹配算法和固件预处理算法。两个算法的有效结合组成一款手机固件的差分压缩优化算法：∆= F₂ – P(F₁), F₂= P(F₁) +∆ 其中P(*)为基于代码映射匹配的固件预处理算法。这个方案在没有对底层的差分压缩引擎做任何改动的情况下极大地提高了压缩率，从软件架构上讲简洁而有效，以数学算法而言非常优美。后来，在行业诸客户对四个主要OTA产商的评估中，我们差分压缩引擎的高压缩率为公司赢得不少订单。

之后，我开始了对差分压缩通用算法的深入研究。在研究了本地差分压缩工具xdelta 、zdelta、bsdiff以及远程差分压缩工具rsync、 RDC之后，我发现所有差分压缩可以用COPY/ADD这两个字符串操作指令模型严格描述：

○ ∆ =F₂- F₁，F₂ = F₁ + ∆ ；

○ F₂- F_{1表示通过比较两个字符串F2和F1之差异而产生COPY和ADD的一个序列∆ 。}

○ 通过以上序列的COPY/ADD操作指令，我们将字符串F₁ 转化成F_2。

差分压缩一个很自然的技术扩展是文件树的差分压缩：如何比较两个文件树的差异，以产生一系列操作指令将一个文件树转化成另一棵树呢？当年（2004年），我们用六个指令ADD、DELETE、MODIFY、COPYNODE、MOVE、RENAME 定义了节点级操作，再用COPY和ADD定义文件（字符串）级操作。但是，有一个技术困难，如何有效地辨识目录或文件的复制、迁移和改名？由于2004年底开始创业，我再也没精力研究这个问题。直到很多年后的疫情期间，我有了很多时间来研究这个问题。2020年中，我提出了目录指纹这个概念，然后设计了目录指纹算法，进而解决了目录或文件的复制、迁移和改名的辨识难题。16年之后，我终于设计出有效的文件树差分压缩算法，从而全面构建起差分压缩理论体系。

这个理论分成两个部分：初等差分压缩理论和高等差分压缩理论。

初等差分压缩理论:

○ 建立基于COPY/ADD字符串操作指令的差分压缩模型；

○ 以COPY/ADD模型统一本地差分压缩算法，譬如xdelta、zdelta、bsdiff等；

○ 以COPY/ADD模型统一远程差分压缩算法，譬如Rsync和RDC；

○ 以COPY/ADD模型提出迭代差分压缩，并给出迭代差分压缩算法。这是有别于本地差分压缩和远程差分压缩的新范式；

○ 以COPY/ADD字符串操作指令模型和三维分类体系（本地/同时同地 vs 远程/同时异地 vs 迭代 /异时同地）建立初等差分压缩理论。

高等差分压缩理论:

○ 建立基于

COPYNODE/MOVE/DELETE/ADD/RENAME/MODIFY节点操作指令的文件树差分压缩模型；

○ 定义文件指纹和目录指纹。引进一个文件指纹算法，给出原创的目录指纹算法；

○ 给出基于文件指纹和目录指纹的COPYNODE/MOVE/RENAME的文件树节点识别算法；

○ 给出基于目录指纹的本地文件树差分压缩算法。

○ 以COPYNODE / MOVE/ DELETE/ ADD/ RENAME/ MODIFY文件树节点操作指令模型、COPY/ADD字符串操作指令模型、三维分类体系建立高等差分压缩理论。

备注：

○ 在高等差分压缩理论里，我们忽略符号链接等实践性系统节点以保证理论的简洁性。我们认为符号链接等的处理可以在实践中作为补充加以实现。

○ 差分压缩理论有很多应用场景，其中一个最重要的应用为数据备份和灾难恢复。

3.字符串近似匹配理论

2005年，我作为联合创始人在硅谷创立了一家数据安全公司，从事数据泄露防护系统（DLP）的研究和开发。DLP系统的核心技术是敏感数据识别技术。我们首次提出了文件指纹这个概念以刻画一个文件不同版本之间的相似性，并设计了DLP行业第一款文件指纹算法，其本质是字符串的近似匹配。三年左右，该初创企业被信息安全头部企业收购。在新公司，由于文件指纹算法得一些缺陷，我又设计了识别能力和效率更高的第二代文件指纹算法。

后来，我在电脑病毒识别算法的研究过程中，接触到另一类文件相似度匹配算法：模糊哈希（包括ssdeep、sdhash、TLSH、Nilsimsa、SimHash）。模糊哈希有别于传统精确匹配的MD5或SHA-1等哈希算法，可以对有细微差别（譬如5%、10%）的两文件做一一匹配。模糊哈希也属于字符串近似匹配的技术范筹，虽然近似匹配能力比文件指纹算法差很多。

疫情期间，我在全面总结两代文件指纹算法以及研究了模糊哈希的相关文献后，总结出字符串近似匹配的六种情况。基于这六种情况，建立了字符串近似匹配理论。在这个理论的指导下，又设计了效率更高的第三代文件指纹算法。

以下是这个理论的简介：

○ 将两个足够长的字符串T₁和T₂的关系分成6 种情形：

○ 相等关系：T₁=T₂；

○ 包含关系：T₁是T₂的子串，或反之；

○ T₁和T₂有相同的足够长的非平凡子串t。

○ 相似关系：T_{1 ≈}T₂；

○ 近似包含关系：T₁跟T₂的一个子串相似，或反之；

○ T₁的非平凡子串t₁相似于T₁的非平凡子串t₂，t₁≈t₂。

○ 用字符串指纹算法定义两个字符串的相似度（0到100%）。

○ 设计以上六个关系的判断算法。

○ 定义近似字符串搜索问题：S为一非平凡字符串集，给定一个非平凡字符串T，在S中找到跟T最相似的字符串t。

○ 设计一个算法解决了近似字符串搜索问题。

○ 定义近似字符串聚类问题：S为一非平凡字符串集，让相似的非平凡字符串聚在一起。

○ 设计一个算法解决了近似字符串聚类问题。

○ 结语：以上六种字符串关系分类法、近似字符串搜索问题、近似字符串聚类问题以及相关算法构成了字符串近似匹配理论。

字符串近似匹配理论有很多应用场景：

○ 一个重要的应用是解决DLP系统的近似字符串搜索问题，其技术我们称之为文件指纹算法。

○ 论文查重系统；

○ 互联网去重系统；

○ 互联网隐私文件追踪和删除系统；

○ 知识产权侵权调查系统：法律诉讼尽调。

○ 知识产权防侵权检测系统：企业并购尽调.

○ 。。。

4.结语

本文回顾了作者过去二十年研究历程中建立的两个信息技术理论体系：差分压缩理论与字符串近似匹配理论。

在差分压缩理论方面，我们从一个具体的工程挑战——消除机器代码的次级变化——出发，建立了代码变化理论，并最终升华到对差分压缩本质的深刻理解：即以COPY/ADD操作为核心的通用模型。这一模型不仅成功统一了本地与远程差分压缩算法，更催生了原创的在字符串近似匹配理论方面，源于数据泄露防护（DLP）的实践需求，我们首创了“文件指纹”概念并设计了系列算法。通过系统性地定义字符串间的六种基本近似关系，我们构建了一个包含相似度量化、关系判定、近似搜索与聚类等核心问题的统一理论框架。这一理论不仅显著提升了文件指纹算法的识别能力和效率（驱动了第三代算法的诞生），更拓展出在论文查重、互联网去重、隐私保护、知识产权尽调等诸多领域的广阔应用前景。“迭代差分压缩”新范式。尤为重要的是，历经十六载的沉淀，通过引入“目录指纹”这一关键概念，我们彻底解决了文件树节点复制、迁移与改名的识别难题，从而构建了涵盖字符串与文件树操作、融合初等与高等差分压缩理论的完整体系。该理论为高效的数据同步、备份与恢复奠定了坚实的基石。