开源软件依赖可满足性识别方法研究与实现

论文摘要

随着网络技术的发展,开放源码软件（Open Source Software, OSS）项目得到快速的发展和普及,软件从传统的集中开发模式向分散式发生了转变,使得源码复用程度大大加强,产生了软件依赖问题。虽然基于开源软件分发系统的软件管理工具在一定程度上能够简单的识别软件依赖,但是处理复杂的依赖关系仍旧存在不足。另一方面分发端软件更新频繁,引起依赖关系不稳定,最终导致分发系统不稳定。本课题基于国家863项目：分布式构件库服务平台支撑技术及应用研究（项目编号：2006AA01Z191）,该项目主要研究软件分发系统技术及其在嵌入式开源软件中的应用。针对分布式构件库服务平台中的开源软件库和构件库具有与开源软件分发端相似的功能,本文研究了开源软件分发系统处理软件依赖关系的原理与局限性,提出了在分发端识别软件依赖可满足性的CNF-SAT解决方法,以提高软件分发系统的稳定性。本文首先分析了开源分发系统基本原理及开源软件本身的特性,研究了处理软件依赖可满足性识别策略,重点研究了基于软件包管理技术的软件依赖识别策略,对现有策略的局限性和不足进行分析。基于上述不足,本文提出了将软件依赖可满足性识别问题转化为CNF-SAT问题的方法,通过求解CNF-SAT问题,识别软件依赖关系中的冲突。本文提出了一整套软件依赖可满足性问题向CNF-SAT问题映射的转化规则,最终以高效的MiniSAT算法实现本文所提出的改进方法,实验结果证明本方法能够提高软件依赖关系识别的效率及分发系统的稳定性,为处理开放源码软件依赖关系提供了高效的解决方法。本文最后对下一步研究进行了展望。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 引言
• 1.1 论文研究背景
• 1.2 开源软件的软件依赖问题研究现状
• 1.3 本文研究的意义和目的
• 1.4 论文结构
• 第2章 开源软件分发系统
• 2.1 开源软件及其特点
• 2.2 软件分发系统模型
• 2.2.1 分发端
• 2.2.2 用户端
• 2.3 主流软件分发系统
• 2.3.1 Apt/dpkg
• 2.3.2 Yum/RPM
• 2.3.3 BSD Ports/Package
• 2.3.4 Portage
• 2.3.5 四种分发系统的对比
• 2.4 本章小结
• 第3章 软件依赖可满足性识别策略研究
• 3.1 软件依赖可满足性定义
• 3.2 软件依赖关系分类
• 3.3 导致软件依赖问题严重的原因
• 3.4 识别软件依赖关系的策略
• 3.4.1 基于软件包的识别策略
• 3.4.2 ad-hoc识别策略
• 3.4.3 基于"分支"的识别策略
• 3.5 本章小结
• 第4章 软件依赖可满足性识别改进方法
• 4.1 改进目标
• 4.2 软件依赖识别问题模型的转化
• 4.3 软件依赖识别改进方法的研究
• 4.3.1 基于图遍历的解决方法
• 4.3.2 基于SAT问题的解决方法
• 4.3.3 改进方法可行性分析
• 4.4 本章小结
• 第5章 软件依赖可满足性识别改进方法的实现
• 5.1 总体模块设计
• 5.2 元数据预处理模块
• 5.3 合取范式转化模块
• 5.4 SAT解析器判断模块
• 5.4.1 蕴含推理模块
• 5.4.2 冲突处理模块
• 5.4.3 决策模块
• 5.5 调试与测试
• 5.5.1 调试结果
• 5.5.2 测试目标
• 5.5.3 测试结果及分析
• 5.6 本章小结
• 第6章 结论与展望
• 6.1 结论
• 6.2 未来工作及展望
• 参考文献
• 致谢
• 攻读硕士期间参加的项目