MOSAIC : structural matching of modified and incomplete code for precise third-party OSS library identification

다국어 초록 (Multilingual Abstract)

Identifying the precise versions of third-party open-source software (OSS) components is fundamental to modern software engineering, impacting everything from long-term maintenance to software supply chain security. However, real-world OSS reuse often involves modified or partially reused code, where hash-based and graph isomorphism approaches break down due to erroneous metadata, scalability constraints, and incomplete function call graphs. We present Mosaic, a framework for robust and scalable version identification in real-world source code. At its core, MOSAIC employs hierarchical divide-and-conquer graph homomorphism (HDC-GH) with progressive matching via leaf-node matching, subgraph isomorphism on local subgraphs, and modified-reuse detection. This structural analysis is further strengthened by identifying version-unique functions and inferring API boundaries, improving precision and recall. Evaluated on 20 large-scale OSS projects, MOSAIC attains an accuracy of 85.1% in TPL version identification, and 76.5% overall accuracy for detecting modified libraries, outperforming a state-of-the-art tool. It processes codebases of up to 15 million lines in under a minute and scales efficiently to much larger projects, producing interpretable, ranked results that establish a practical foundation for automated SBOM generation and resilient supply chain security.

국문 초록 (Abstract)

서드파티 오픈소스 소프트웨어(OSS) 컴포넌트의 정확한 버전 식별은 현대 소프트웨어 엔지니어링의 핵심으로, 장기적인 유지보수부터 소프트웨어 공급망 보안에 이르기까지 모든 것에 영향을 미칩니다. 하지만 실제 OSS 재사용은 종종 수정되거나 부분적으로 재사용된 코드를 포함하며, 이 경우 잘못된 메타데이터, 확장성 제약, 불완전한 function call graph로 인해 hash 기반 및 graph isomorphism 접근법이 실패합니다. 본 연구에서는 실제 소스 코드에서 강건하고 확장 가능한 버전 식별을 위한 프레임워크인 MOSAIC을 제시합니다. MOSAIC의 핵심은 leaf-node matching을 통한 progressive matching, 지역 subgraph에서의 subgraph isomor- phism, modified-reuse detection을 포함한 hierarchical divide-and-conquer graph homomorphism(HDC-GH)을 사용합니다. 이러한 구조적 분석은 version-unique function 식별 및 API boundary 추론을 통해 더욱 강화되어 정밀도와 재현율을 향상시킵니다. 20개의 대규모 OSS 프로젝트에 대한 평가에서 MOSAIC은 TPL 버전 식별에서 85.1%의 정확도와 수정된 라이브러리 탐지에서 76.5%의 전체 정확도를 달성하여 최신 도구를 능가하는 성능을 보였습니다. 1500만 라인의 코드베이스를 1분 이내에 처리하고 훨씬 더 큰 프로젝트로 효율적으로 확장되며, 자동화된 SBOM 생성 및 복원력 있는 공급망 보안을 위한 실용적 기반을 구축하는 해석 가능하고 순위가 매겨진 결과를 생성합니다.

목차 (Table of Contents)

• 1. INTRODUCTION 1
• 2. TERMINOLOGY 4
• 3. PROBLEM STATEMENT 5
• 3.1 Motivating Example 6
• 4. METHODOLOGY 9
• 4.1 FCG Database Construction 9
• 4.2 Third-Party Library Origin Determination and Candidate Filtering 10
• 4.2.1 Majority Voting within File for Precise TPL Identification. 11
• 4.2.2 Region Segmentation and Significance Filtering. 11
• 4.3 HDC-GH 12
• 4.3.1 Stage 1: Leaf Node Matching. 13
• 4.3.2 Stage 2: Subgraph Isomorphism. 13
• 4.3.3 Stage 3: Modified-Reuse Detection. 13
• 4.3.4 Multi-Stage Matching for Reuse Types. 15
• 4.4 Signature Analysis 16
• 4.4.1 Version-Unique Function Detection. 17
• 4.4.2 API Boundary Recognition from Call Relations. 17
• 4.5 TPL Version Scoring 18
• 4.5.1 Final Version Similarity Score. 18
• 4.5.2 Rank-Based Version Selection. 19
• 5. EVALUATION 20
• 5.1 Evaluation Settings 21
• 5.2 RQ1: Detection Accuracy 23
• 5.3 RQ2: Effectiveness of Design Choices 27
• 5.4 RQ3: Robustness and Scalability 28
• 6. DISCUSSION 34
• 7. THREATS TO VALIDITY 36
• 8. RELATED WORK 37
• 9. CONCLUSION 39
• References 41
• 논문요약 46