[go: up one dir, main page]

CN119903529A - 基于函数结构信息的c/c++源代码第三方库重用检测方法 - Google Patents

基于函数结构信息的c/c++源代码第三方库重用检测方法 Download PDF

Info

Publication number
CN119903529A
CN119903529A CN202510105000.6A CN202510105000A CN119903529A CN 119903529 A CN119903529 A CN 119903529A CN 202510105000 A CN202510105000 A CN 202510105000A CN 119903529 A CN119903529 A CN 119903529A
Authority
CN
China
Prior art keywords
function
reuse
tpl
feature
source code
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202510105000.6A
Other languages
English (en)
Inventor
王俊峰
贾昀峰
吴鹏
方智阳
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sichuan University
Original Assignee
Sichuan University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sichuan University filed Critical Sichuan University
Priority to CN202510105000.6A priority Critical patent/CN119903529A/zh
Publication of CN119903529A publication Critical patent/CN119903529A/zh
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/50—Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
    • G06F21/57—Certifying or maintaining trusted computer platforms, e.g. secure boots or power-downs, version controls, system software checks, secure updates or assessing vulnerabilities
    • G06F21/577—Assessing vulnerabilities and evaluating computer system security
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/30—Creation or generation of source code
    • G06F8/36—Software reuse
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/70—Software maintenance or management
    • G06F8/75—Structural analysis for program understanding
    • G06F8/751—Code clone detection
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
    • Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Computer Security & Cryptography (AREA)
  • Computing Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本发明涉及软件开发及软件供应链安全技术领域，公开了基于函数结构信息的C/C++源代码第三方库重用检测方法，本方法通过构建基于开源软件函数AST结构的TPL向量索引库；在向量索引库中，采用异常值检测方法过滤重用频率超过正常频率范围的公共函数；并使用动态占比筛选策略有效过滤误识别的重用TPL候选项，得到更为准确的重用TPL结果。本发明显著提升了TPL重用检测的鲁棒性和准确性，有效减少漏报和误报；同时，本方法相较于传统方法具有更高的检测效率以及更低的存储需求。

Description

基于函数结构信息的C/C++源代码第三方库重用检测方法
技术领域
本发明涉及软件开发及软件供应链安全技术领域，具体涉及基于函数结构信息的C/C++源代码第三方库重用检测方法。
背景技术
开源软件(Open-source software，OSS)数量随着GitHub等远程代码仓库的普及而急剧膨胀，以安装依赖、API调用、项目fork、文件拷贝、代码克隆等多种代码重用手段使第三方库(Third-party libraries，TPL)的使用愈发普遍。特别在C/C++项目中，为避免重复劳动，开发者常利用代码克隆引入所需TPL，并对其进行修改以满足业务需求。以上情况为准确识别TPL工作带来全新挑战，也扩展了软件潜在攻击面。全面追踪软件TPL重用情况至关重要，软件供应链的安全直接关系软件产品的安全性与可靠性。因此，检测软件中重用TPL的软件组成分析(Software composition analysis，SCA)技术成为研究热点，作为及时发现软件安全风险并降低危害的有效手段。
在SCA实践中，OSSPOLICE尝试使用目录结构等轻量级特征来构建特征库，但当项目结构变更时可能出现检测失效、鲁棒性不足的问题。Woo等提出的CENTRIS通过分段OSS源代码、剔除冗余函数并利用模糊哈希技术，提高了在少量修改的重用场景下TPL检测的精确性；尽管如此，在面临较多文本修改时(例如在julius项目中的tinyfiledialogs库的函数，与Github上的原始函数存在差异)该方法可能发生失效，产生假阴性结果。OSSFP引入了针对公共函数和琐碎函数的过滤方法，通过为每个TPL的核心函数构建哈希指纹索引，提升了检测性能与精确性；然而，OSSFP假设重用TPL中存在某些函数未被更改，因此当发生大面积函数修改时(例如，SQLiteCpp项目通过sqlite3.c源文件重用了sqlite库，其中所有函数都添加了新的访问修饰符)同样会面临鲁棒性不足问题，导致检测失效。
此外，观察到CENTRIS并未考虑干扰函数的影响，易产生较多假阳性。而OSSFP通过固定频率阈值筛选公共函数，实际中存在过滤不精确问题；例如，Boost库中包含大量公共函数，而xxhash库中则几乎没有，OSSFP认为两者的公共函数应当以相同比例进行过滤。
通过分析现有静态SCA技术，发现其在检测鲁棒性和干扰函数处理上仍存不足：(1)TPL特征的鲁棒性不足：如CENTRIS、OSSFP等工作依赖函数文本哈希特征，面临TypeⅡ、TypeⅢ代码克隆(例如变量名或代码行修改)，易产生假阴性(FN)；(2)干扰函数过滤不精确：CENTRIS未充分考虑干扰函数，导致假阳性(FP)较多；而OSSFP通过固定频率阈值筛选公共函数，实际中存在过滤不精确问题。
为此，提出基于函数结构信息的C/C++源代码第三方库重用检测方法，以解决上述问题。
发明内容
针对上述问题，本发明的目的在于提供基于函数结构信息的C/C++源代码第三方库重用检测方法，通过构建基于AST结构的特征向量索引库，并结合异常检测技术与动态占比筛选策略，显著提升了TPL重用检测的鲁棒性和准确性，有效减少漏报和误报，技术方案如下：
基于函数结构信息的C/C++源代码第三方库重用检测方法，包括以下步骤：
步骤S1、收集大规模开源软件不同版本的源代码，并对源代码进行预处理，预处理包括以下步骤：
S11、对源代码进行函数切分，并提取源代码的函数AST结构；
S12、根据函数AST结构中节点类型的度数和次序，将函数AST结构解析为两种不同结构特征的向量，并对两向量进行特征拼接生成函数特征向量；
步骤S2、在源代码切分出的函数集合中，基于函数AST结构的结构复杂度过滤通用结构函数；
步骤S3、使用函数特征向量，通过哈希匹配为每个TPL构建函数特征字典；合并所有TPL的函数特征字典生成向量索引库；在向量索引库的合并过程中，记录所有函数克隆对并存储为函数克隆对集合；
步骤S4、基于函数克隆对集合获取每个函数的重用频率；在向量索引库中，过滤重用频率超过正常频率范围的公共函数，获取核心向量索引库；
步骤S5、基于核心向量索引库，采用近似最近邻算法对待测软件进行TPL重用检测，获取重用TPL候选项；根据重用TPL候选项的函数特征占比，过滤误识别的重用TPL候选项，进而确定重用TPL检测结果。
进一步地，所述步骤S12，具体包括：
根据函数AST结构中节点类型的度数和次序，使用TreeCen算法将函数AST结构解析为两种不同结构特征的向量，并对两向量进行特征拼接生成函数特征向量，计算公式如下：
v＝βv1+(1-β)v2,β∈[0,1]
其中，v1代表由各节点类型的度数之和得到的向量，v2代表由各节点类型次序之和得到的向量，β表示在特征拼接中v1所占的权重。
进一步地，所述步骤S2，包括以下步骤：
S21、函数的结构复杂度C定义为：
C＝|{ti|ci≥1,i＝1,2,…,n}|
其中，ti为函数AST结构中第i种结构类型，ci为函数AST结构中第i种结构类型的出现次数；函数AST结构中出现次数大于等于1的结构类型种类总数即为函数的结构复杂度；
S22、在源代码切分出的函数集合中，统计每个函数AST结构中不同结构类型的出现次数，获取每个函数的结构复杂度C；
S23、剔除函数集合中结构复杂度C小于预设阈值的通用结构函数；其中，预设阈值
进一步地，所述步骤S3，包括以下步骤：
S31、使用函数文本哈希值作为字典的键，使用最早提交时间的函数特征作为字典的值，通过哈希匹配为每个TPL构建函数特征字典；其中，函数特征定义为一个描述函数属性信息的元组：{函数文本哈希值，函数地址，提交时间，函数特征向量}；
S32、从所有TPL的函数特征字典中提取函数特征向量；通过近似最近邻算法对所有函数特征向量进行比较去重，优先保留提交时间更早的函数特征向量，进而合并所有TPL的函数特征字典生成向量索引库；在向量索引库的合并过程中，将所有相似的函数对fa、fb以函数克隆对(fa,fb)的形式存储为函数克隆对集合，并确保提交时间更早的函数为fa，而fb则为其克隆者。
进一步地，所述步骤S4，包括以下步骤：
S41、使用函数克隆对集合构造并查集DSU，以最早提交时间的函数作为并查集每个集合的根节点，以与最早提交时间的函数存在克隆关系的其余函数作为并查集每个集合的子节点；通过路径压缩算法查询并查集中各个集和中子节点的数量，获取每个函数的重用频率；
S42、采用基于统计分布的Z-score异常检测方法，计算函数重用频率的标准化距离，计算公式如下：
Z(Xf)＝(Xf-μ)/σ
其中，Xf为函数f的重用频率值；Z(Xf)为标准化距离；μ与σ分别为函数f所属TPL中函数重用频率的均值与标准差；
正常频率范围内的核心函数特征集合的筛选条件如下：
B′＝{f∈B|Z(Xf)≤τ}
其中，B表示函数f所属TPL的函数特征集合，B′表示在B中正常频率范围内的函数特征集合，阈值τ设为1；
在向量索引库中，根据筛选条件过滤重用频率超过正常频率范围的公共函数特征集合，保留正常频率范围内的核心函数特征集合，获取核心向量索引库；
进一步地，所述步骤S5，包括以下步骤：
S51、对待测软件的源代码使用步骤S1的相同方法进行预处理，得到待测函数特征向量；
S52、在核心向量索引库中，采用近似最近邻算法查找与待测函数特征向量近似匹配的函数特征向量，并将查找到的函数特征向量对应的函数集合所属的第三方库集合作为重用TPL候选项；
S53、计算所有重用TPL候选项对应的函数特征占比，计算公式如下：
其中，p(Tj)为第j个重用TPL候选项对应的函数特征占比，Tj为第j个重用TPL候选项，为待测软件中与Tj匹配的函数特征集合，为核心向量索引库中Tj对应的函数特征集合；
对重用TPL候选项，按照其函数特征占比从小到大的顺序进行排序，并移除排序结果中排名在前10％且函数特征占比低于2％的TPL候选项，得到重用TPL检测结果。
本发明与现有技术相比，具有如下优点和有益效果：
本发明通过开源软件源代码的函数AST结构获取函数特征向量；使用函数特征向量，为每个TPL构建函数特征字典；合并所有TPL的特征字典生成向量索引库，并记录函数克隆对集合；基于函数克隆对集合获取每个函数的重用频率，并过滤重用频率异常的公共函数，获取核心向量索引库；基于核心向量索引库，对待测软件进行TPL重用检测，并根据重用TPL候选项的函数特征占比过滤误判的TPL候选项，确定重用TPL函数集合。本发明基于函数AST结构特征，显著提升了在修改的重用场景下TPL检测的鲁棒性，有效减少漏报；基于异常检测技术过滤频率超过正常范围的公共函数，减少了干扰函数的影响，提高了TPL重用检测的准确性，有效减少误报；采用动态占比筛选策略有效过滤误识别的重用TPL候选项，进一步提高了TPL重用检测的准确性；同时，本方法相较于传统方法具有更高的检测效率以及更低的存储需求。
附图说明
图1为本方法的总体框架示意图。
图2为结构向量编码示意图。
图3为特征字典构建伪代码。
图4为向量索引合并伪代码。
图5为基于异常值检测的公共函数过滤方法流程图。
图6为不同方法检测结果准确性对比图。
具体实施方式
下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整的描述，以便对本发明的构思、所解决的技术问题、构成技术方案的技术特征和带来的技术效果有更进一步的了解。
本方法的总体流程图如图1所示，具体包括以下步骤：
步骤S1、函数特征提取；收集大规模开源软件OSS(Open Source Software，OSS)及其不同版本的源代码，并对源代码进行预处理，包括以下步骤：
S11、OSS数据收集；利用Git API或者爬虫广泛收集有效的开源代码repo仓库；例如通过git tag命令获取仓库的版本tag列表及其发布时间，利用git diff命令识别相邻版本之间的文件变更情况。
S12、OSS数据预处理，包括以下步骤：
S121、对每个源代码文件，消除不必要的注释与空行，避免无效信息干扰；
S122、基于公开的源代码解析工具Tree-sitter，对源代码进行函数切分并提取源代码的函数AST结构；
S123、根据函数AST结构中节点类型的度数和次序，将函数AST结构解析为两种不同结构特征的向量，并对两向量进行特征拼接生成函数特征向量；
如图2所示，采用TreeCen算法高效完成函数AST结构信息到定长向量的转换；其中，特征向量维度需由必要的C/C++AST节点类型数量决定，可通过解析工具的配置文件node-types.json获取；
为应对TypeⅡ、TypeⅢ代码克隆问题(例如变量名修改、代码相邻节点位置互换)中节点度数特征的局限性，本方法对源代码的函数AST结构中节点类型的度数(degree)和次序(sequence)解析出两种不同结构特征的向量，随后通过特征拼接生成最终的函数特征向量v，计算公式如下：
v＝βv1+(1-β)v2,β∈[0,1]
其中，v1代表由各节点类型的度数之和得到的向量；v2代表由各节点类型次序之和得到的向量；β表示在特征拼接中v1所占的权重；
本发明基于函数AST结构特征，解决了TypeⅡ、TypeⅢ代码克隆(例如变量名修改、代码相邻节点位置互换)的失效问题，显著提升了在修改的重用场景下TPL检测的鲁棒性，有效减少漏报情况。
步骤S2、在源代码切分出的函数集合中，基于函数AST结构的结构复杂度过滤通用结构函数，减少误报影响；
参考可维护性指数，本方法设计了一种基于结构复杂度的度量过滤机制，包括以下步骤：
S21、对于一个函数，其AST结构中的结构类型集合为A＝{t1,t2,…,tn}，其中每个结构类型ti的出现次数为ci(ci≥0)，则该函数的结构复杂度C定义为：
C＝|{ti|ci≥1,i＝1,2,…,n}|
其中，ci≥1表示该结构类型ti在函数的AST中至少出现一次；若ci＝0，则该结构类型不计入复杂度计算；因此，当该函数实际使用到的结构类型种类较少时，其结构复杂度C较低，反之则较高。
S22、在源代码切分出的函数集合中，统计每个函数AST结构中不同结构类型的出现次数，获取每个函数的结构复杂度C。
S23、设定一个预定义阈值当函数的结构复杂度时，该函数被标记为通用结构函数或简单函数，并从函数集合中剔除；其中，
本发明基于函数AST结构的结构复杂度，过滤干扰函数(通用结构函数或简单函数)，提高了TPL重用检测的准确性，有效减少误报情况。
步骤S3、使用函数特征向量，通过哈希匹配为每个TPL构建函数特征字典；合并所有TPL的函数特征字典生成向量索引库；在向量索引库的合并过程中，记录所有函数克隆对并存储为函数克隆对集合，包括以下步骤：
S31、特征字典构建；由于不同版本TPL中存在大量的重复函数，本发明采用哈希匹配为每个TPL快速构建独立的特征字典，实现函数去重；其中，特征字典的键为函数文本哈希值，值为最早提交时间的函数特征；其中，函数特征定义为一个描述函数属性信息的元组：{函数文本哈希值，函数地址，提交时间，函数特征向量}；
如图3所示，描述了单个TPL函数特征字典的构建过程。其中D表示一个TPL的特征字典，F表示特定的函数特征，VF为某个版本的函数特征集合，VFL是该TPL所有版本函数属性信息的列表；为了确保存储的函数特征是最早提交的版本，算法通过以下策略执行操作：如果当前函数F的文本哈希值尚未记录于字典D，则直接F追加存储到字典D中；否则，比较新函数F的提交时间；如果F的提交时间更早，则更新字典D中的记录。
S32、向量索引合并；引入基于向量数据库的ANN搜索，从所有TPL的函数特征字典中提取函数特征向量进行比较和去重；去重过程中，优先保留提交时间更早的函数特征向量，简化索引，合并生成向量索引库，并有效消除不同TPL间的重复函数和相似函数；如图4所示，通过遍历全部TPL的函数特征字典，最终合并为一个全局向量索引库IM；其中，DL为函数特征字典D的列表；RL表示函数特征字典D中的函数特征向量集合在IM中的匹配结果；FT和FM分别表示被比较的函数特征及其相似匹配结果；δ为设定的向量相似度阈值；
该过程中，记录下函数克隆对的检索日志，用于后续的公共函数过滤阶段；例如，对于两个相似函数f1和f2，假设f1提交时间早于f2，则可能存在两种情况：f1先被检测到，或者f2先被检测到，而后一种情况还需要更新IM；无论顺序如何，均需记录所有函数克隆对(f1,f2)并存储为函数克隆对集合，还需确保提交时间更早的函数为f1，而f2则为其克隆者。
步骤S4、基于函数克隆对集合获取每个函数的重用频率；在向量索引库中，过滤重用频率超过正常频率范围的公共函数，获取核心向量索引库，包括以下步骤：
S41、基于路径压缩的频率统计；如图5所示，基于函数克隆对集合，构造并查集(Union-find disjoint sets，DSU)的频率统计结构；其中，每个集合的根节点为最早提交时间的函数，称为根函数；每个集合的子节点为与根函数存在着克隆关系的其余函数；利用路径压缩算法高效查询DSU中各个集合的成员(子节点)数量，从而获得每个根函数的重用频率；随后，对每个TPL统计出根函数频率表，由此得到每个函数的重用频率。
S42、基于Z-score的公共函数过滤；为了高效过滤公共函数，本方法统计所有函数的重用频率，并将公共函数过滤问题转化为异常检测问题；即当某个函数的重用频率显著偏离正常频率范围时，则视其为异常值，判定其为公共函数；由于此处为单一维度异常值检测，选用基于统计分布的Z-score异常检测方法，首先计算每个函数重用频率的标准化距离Z(Xf)，计算公式如下：
Z(Xf)＝(Xf-μ)/σ
其中，Xf为函数f的重用频率值；Z(Xf)为标准化距离；μ与σ分别为函数f所属TPL中函数重用频率的均值与标准差；
如果Z(Xf)超过指定的距离阈值τ，则将其视为异常值并过滤；考虑到公共函数通常表现为高频率特征，只关注重用频率值过高的函数，低于均值μ的重用频率值也被视为合理范围；因此，正常频率范围内的核心函数特征集合B′的筛选条件如下：
B′＝{f∈B|Z(Xf)≤τ}
其中，B表示函数f所属TPL的函数特征集合，B′表示在B中正常频率范围内的函数特征集合，阈值τ设为1；
在向量索引库中，根据筛选条件过滤重用频率超过正常频率范围的公共函数特征集合，提取到每个TPL的核心函数特征集合，获取核心向量索引库；
本发明基于异常检测技术过滤频率超过正常范围的公共函数，减少了干扰函数(公共函数)的影响，提高了TPL重用检测的准确性，有效减少误报情况。
步骤S5、待测软件TPL重用检测；本步骤目标为基于向量索引库，从待测软件项中识别出函数特征的近似最近邻函数集合，从而确定重用TPL候选项；由于数据规模限制，TPL候选结果中可能包含不准确的检测项，因此设计了重用TPL候选项的动态占比过滤策略，进而得到更为准确的重用TPL检测结果，包括以下步骤：
S51、对待测软件的源代码使用步骤S1的相同方法进行预处理，得到待测函数特征向量；
待测软件的源代码整体输入到系统中，并使用步骤S1的相同方法进行预处理，对待测软件源代码的每个函数进行切分，并提取待测函数AST结构，对待测函数AST结构进行特征提取，生成待测函数特征向量。
S52、在核心向量索引库中，采用近似最近邻算法查找与待测函数特征向量近似匹配的函数特征向量，并将查找到的函数特征向量对应的函数集合所属的第三方库集合作为重用TPL候选项。
S53、根据重用TPL候选项的函数特征占比，过滤误识别的重用TPL候选项，进而确定最终的重用TPL检测结果；
采用一种动态占比阈值策略，优化了重用TPL候选项的筛选过程；首先，计算所有重用TPL候选项对应的函数特征占比，计算公式如下：
其中，p(Tj)为第j个重用TPL候选项对应的函数特征占比，Tj为第j个重用TPL候选项，为待测软件中与Tj匹配的函数特征集合，为核心向量索引库中Tj对应的函数特征集合；
对重用TPL候选项，按照其函数特征占比从小到大的顺序进行排序；移除排序结果中排名在前10％且函数特征占比低于2％的TPL候选项，得到更为准确的重用TPL检测结果，并输出详细的TPL检测报告；
传统方法移除所有函数特征占比低于2％的TPL候选项，容易过滤掉一些正确的TPL候选项，从而降低TPL重用检测的准确性；因此，该策略旨在考虑函数特征占比的最小前10％，尽可能过滤因偶然相似性而被误识别的TPL候选项，在过滤和正确性之间达到一个平衡，并保留具有较高可靠性和显著性特征的重用TPL候选项，进一步提高了TPL重用检测的准确性。
步骤S6、基于100个知名开源项目的验证数据集，评估TPLADD、CENTRIS和OSSFP方法的TPL重用检测准确性；对TPLADD和CENTRIS均设计了候选结果过滤模块，实验在开启和未开启过滤模块的情况下分别进行，并记录两种场景结果；开启过滤模块的结果以“(f)”表示，例如TPLADD(f)代表开启过滤TPL候选项，TPLADD代表未开启过滤TPL候选项；
如图6所示，在均开启过滤模块的情况下，相较于现有方法CENTRIS，本方法TPLADD在精确率和召回率上分别提升了3.88％和2.76％，可见本方法显著提升了TPL重用检测的准确性；其中，图中TP为真阳性，PRE为精确率，REC为召回率，F1为F1值；
同时，时间上，本方法较CENTRIS方法速度提高了21.9％，平均每检测出一个TPL耗时仅为0.42秒，显著提升了TPL重用检测的检测效率；空间上，本方法仅需保留总体函数特征的0.41％，与CENTRIS和OSSFP相比，向量索引库的规模只有CENTRIS的20％，显著降低了TPL重用检测的存储需求。
以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (6)

1.基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，包括以下步骤：
步骤S1、收集大规模开源软件不同版本的源代码，并对源代码进行预处理，预处理包括以下步骤：
S11、对源代码进行函数切分，并提取源代码的函数AST结构；
S12、根据函数AST结构中节点类型的度数和次序，将函数AST结构解析为两种不同结构特征的向量，并对两向量进行特征拼接生成函数特征向量；
步骤S2、在源代码切分出的函数集合中，基于函数AST结构的结构复杂度过滤通用结构函数；
步骤S3、使用函数特征向量，通过哈希匹配为每个TPL构建函数特征字典；合并所有TPL的函数特征字典生成向量索引库；在向量索引库的合并过程中，记录所有函数克隆对并存储为函数克隆对集合；
步骤S4、基于函数克隆对集合获取每个函数的重用频率；在向量索引库中，过滤重用频率超过正常频率范围的公共函数，获取核心向量索引库；
步骤S5、基于核心向量索引库，采用近似最近邻算法对待测软件进行TPL重用检测，获取重用TPL候选项；根据重用TPL候选项的函数特征占比，过滤误识别的重用TPL候选项，进而确定重用TPL检测结果。
2.如权利要求1所述的基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，所述步骤S12，具体包括：
根据函数AST结构中节点类型的度数和次序，使用TreeCen算法将函数AST结构解析为两种不同结构特征的向量，并对两向量进行特征拼接生成函数特征向量，计算公式如下：
v＝βv1+(1-β)v2,β∈[0,1]
其中，v1代表由各节点类型的度数之和得到的向量，v2代表由各节点类型次序之和得到的向量，β表示在特征拼接中v1所占的权重。
3.如权利要求1所述的基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，所述步骤S2，包括以下步骤：
S21、函数的结构复杂度C定义为：
C＝|{ti|ci≥1,i＝1,2,…,n}|
其中，ti为函数AST结构中第i种结构类型，ci为函数AST结构中第i种结构类型的出现次数；函数AST结构中出现次数大于等于1的结构类型种类总数即为函数的结构复杂度；
S22、在源代码切分出的函数集合中，统计每个函数AST结构中不同结构类型的出现次数，获取每个函数的结构复杂度C；
S23、剔除函数集合中结构复杂度C小于预设阈值的通用结构函数；其中，预设阈值
4.如权利要求1所述的基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，所述步骤S3，包括以下步骤：
S31、使用函数文本哈希值作为字典的键，使用最早提交时间的函数特征作为字典的值，通过哈希匹配为每个TPL构建函数特征字典；其中，函数特征定义为一个描述函数属性信息的元组：{函数文本哈希值，函数地址，提交时间，函数特征向量}；
S32、从所有TPL的函数特征字典中提取函数特征向量；通过近似最近邻算法对所有函数特征向量进行比较去重，优先保留提交时间更早的函数特征向量，进而合并所有TPL的函数特征字典生成向量索引库；在向量索引库的合并过程中，将所有相似的函数对fa、fb以函数克隆对(fa,fb)的形式存储为函数克隆对集合，并确保提交时间更早的函数为fa，而fb则为其克隆者。
5.如权利要求1所述的基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，所述步骤S4，包括以下步骤：
S41、使用函数克隆对集合构造并查集DSU，以最早提交时间的函数作为并查集每个集合的根节点，以与最早提交时间的函数存在克隆关系的其余函数作为并查集每个集合的子节点；通过路径压缩算法查询并查集中各个集和中子节点的数量，获取每个函数的重用频率；
S42、采用基于统计分布的Z-score异常检测方法，计算函数重用频率的标准化距离，计算公式如下：
Z(Xf)＝(Xf-μ)/σ
其中，Xf为函数f的重用频率值；Z(Xf)为标准化距离；μ与σ分别为函数f所属TPL中函数重用频率的均值与标准差；
正常频率范围内的核心函数特征集合的筛选条件如下：
B′＝{f∈B|Z(Xf)≤τ}
其中，B表示函数f所属TPL的函数特征集合，B′表示在B中正常频率范围内的函数特征集合，阈值τ设为1；
在向量索引库中，根据筛选条件过滤重用频率超过正常频率范围的公共函数特征集合，保留正常频率范围内的核心函数特征集合，获取核心向量索引库。
6.如权利要求1所述的基于函数结构信息的C/C++源代码第三方库重用检测方法，其特征在于，所述步骤S5，包括以下步骤：
S51、对待测软件的源代码使用步骤S1的相同方法进行预处理，得到待测函数特征向量；
S52、在核心向量索引库中，采用近似最近邻算法查找与待测函数特征向量近似匹配的函数特征向量，并将查找到的函数特征向量对应的函数集合所属的第三方库集合作为重用TPL候选项；
S53、计算所有重用TPL候选项对应的函数特征占比，计算公式如下：
其中，p(Tj)为第j个重用TPL候选项对应的函数特征占比，Tj为第j个重用TPL候选项，为待测软件中与Tj匹配的函数特征集合，为核心向量索引库中Tj对应的函数特征集合；对重用TPL候选项，按照其函数特征占比从小到大的顺序进行排序，并移除排序结果中排名在前10％且函数特征占比低于2％的TPL候选项，得到重用TPL检测结果。
CN202510105000.6A 2025-01-23 2025-01-23 基于函数结构信息的c/c++源代码第三方库重用检测方法 Pending CN119903529A (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202510105000.6A CN119903529A (zh) 2025-01-23 2025-01-23 基于函数结构信息的c/c++源代码第三方库重用检测方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202510105000.6A CN119903529A (zh) 2025-01-23 2025-01-23 基于函数结构信息的c/c++源代码第三方库重用检测方法

Publications (1)

Publication Number Publication Date
CN119903529A true CN119903529A (zh) 2025-04-29

Family

ID=95464285

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202510105000.6A Pending CN119903529A (zh) 2025-01-23 2025-01-23 基于函数结构信息的c/c++源代码第三方库重用检测方法

Country Status (1)

Country Link
CN (1) CN119903529A (zh)

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120159434A1 (en) * 2010-12-20 2012-06-21 Microsoft Corporation Code clone notification and architectural change visualization
CN115455417A (zh) * 2022-09-22 2022-12-09 中国电子科技网络信息安全有限公司 一种基于属性图的同源性代码检测方法及系统
CN117591172A (zh) * 2023-11-20 2024-02-23 浙江大学 一种基于向量数据库的特征融合代码克隆检测方法及装置
US20240411897A1 (en) * 2023-06-12 2024-12-12 Endor Labs Inc Identifying and addressing potential vulnerabilities in third-party code

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20120159434A1 (en) * 2010-12-20 2012-06-21 Microsoft Corporation Code clone notification and architectural change visualization
CN115455417A (zh) * 2022-09-22 2022-12-09 中国电子科技网络信息安全有限公司 一种基于属性图的同源性代码检测方法及系统
US20240411897A1 (en) * 2023-06-12 2024-12-12 Endor Labs Inc Identifying and addressing potential vulnerabilities in third-party code
CN117591172A (zh) * 2023-11-20 2024-02-23 浙江大学 一种基于向量数据库的特征融合代码克隆检测方法及装置

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
贾昀等: "TPLADD：高鲁棒性与高精度的C_C++第三方库检测方法", 《计算机科学与探索》, vol. 17, no. 7, 7 January 2025 (2025-01-07), pages 1969 - 1980 *

Similar Documents

Publication Publication Date Title
CN110888849B (zh) 一种在线日志解析方法、系统及其电子终端设备
CN112800113B (zh) 一种基于数据挖掘分析技术的招投标审计方法及系统
US9442991B2 (en) Ascribing actionable attributes to data that describes a personal identity
US20190228085A1 (en) Log file pattern identifier
CN110659282A (zh) 数据路由的构建方法、装置、计算机设备和存储介质
CN117648214A (zh) 一种异常日志处理方法及装置
CN115953123A (zh) 机器人自动化流程的生成方法、装置、设备及存储介质
CN118606520A (zh) 一种软件供应链恶意开源项目监测预警方法及装置
CN118093735A (zh) 多源异构数据的流式数据仓库的实现方法、系统和介质
CN113239365A (zh) 一种基于知识图谱的漏洞修复方法
CN116738979A (zh) 基于核心数据识别的电网数据搜索方法、系统及电子设备
CN119441410A (zh) 一种基于大语言模型工作流程的运维问答系统及方法
CN114969041A (zh) 一种多源主附实体同一性甄别及数据自补的处理方法
CN119903529A (zh) 基于函数结构信息的c/c++源代码第三方库重用检测方法
CN114968258B (zh) 面向代码溯源的克隆代码继承关系判定方法、系统及介质
Pan et al. An Intelligent Framework for Log Anomaly Detection Based on Log Template Extraction
Zhang et al. Research on data cleaning method based on SNM algorithm
CN114297729A (zh) 一种配置管理数据库的审计方法、系统及相关装置
CN118898068B (zh) 一种基于相似度计算的软件与进程匹配方法
CN110781309A (zh) 一种基于模式匹配的实体并列关系相似度计算方法
Chantaranimi¹ et al. Strategies in Entity Matching
LESTANTO et al. Development of a Data Cleaning System for Consumer Master Data using Sorted Neighborhood and N-Gram Methods
CN119128237A (zh) 基于动态规则的字段分级方法、装置、设备及存储介质
CN119515520A (zh) 事件故障根源定位方法及装置
CN117762774A (zh) 一种基于隐式关系和量化调用关系增强的缺陷定位方法

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination