程序动态执行路径剖析方法研究

Path profiling is critical for understanding dynamic behaviors of large programs. It plays an important role in a wide range of software development processes and large applications such as testing, debugging and error reporting, and program analysis. However, there are still many critical issues in current path profiling methods.. In our work, we will research on the following three issues: 1)dynamic path profiling method without static program analysis techniques; 2)adpative path encoding method with dynamic profiles; 3)inter-threads path profiling mehtod for multi-threaded programs. . We will base on our research experience in program analysis and dynamic optimization, study dynamic path encoding method, adaptive encoding method, and inter-threads path encoding method. In our work, we will propose a dynamic and adaptive path encoding method, and implement a path profiling prototype system.

动态执行路径信息对深入理解程序执行行为能够起到非常重要的作用。但是如何高效地获取程序执行路径剖析，至今仍是一个开放的问题。 . 本项目针对目前执行路径剖析研究中存在的挑战性问题，在以下三点寻求突破：1）研究不依赖于静态分析技术的执行路径动态编码方法；2）利用动态剖析反馈信息，研究自适应的路径编码方法，以降低获取动态执行路径剖析带来的时间和空间开销；3）针对多线程程序的特点，研究获取多线程程序线程间执行路径剖析的方法。. 本项目的特点在于充分结合申请人在程序分析和动态优化方面的研究基础，针对执行路径剖析方法在实际应用中存在的关键性问题，对执行路径动态编码方法、自适应路径编码方法和线程间执行路径编码方法等三项内容进行创新研究，提出并实现一个可以应用于多线程程序的、低开销的执行路径动态自适应编码方法，并将本项目的研究成果集成到一个原型系统中，为以后的相关研究工作提供一个基础平台。

函数调用栈(即函数调用路径)，是用户栈上的活跃函数集合。它可以有效地反映程序中的过程间执行路径，从而可以帮助程序开发或分析人员更好的理解程序结构和程序动态执行行为。现在，函数调用路径信息已被广泛应用在了很多领域，比如程序动态执行信息分析、程序调试和错误报告、软件测试、安全保证、事件记录等。例如，在程序调试过程中，程序员会通过遍历栈方法获取中断点的函数调用栈，来辅助程序调试。 . 本项目中，我们在已有方法的基础上提出了一种动态自适应 的函数调用路径编码方法(Dynamic and Adaptive Calling Context Encoding，缩写为DACCE)。它可以有效地获取多线程程序的函数调用路径，而且适用于大多数编程语言生成的应用程序。DACCE使用了二进制插桩的方式，在编码时不需要知道完整的函数调用图，并会在程序执行过程中根据收集的信息调整编码。与已有方法相比，DACCE不需要使用训练执行来获取程序静态剖析信息，而且不会对编译优化产生影响。另外，DACCE是以共享库的形式实现的，因此它可以非常方便的应用在其它工具中。另外，DACCE不仅可以获取单线程程序的函数调用路径信息，还可以有效的获取Pthread等多线程程序的完整函数调用路径信息。. 本项目的主要贡献和成果有: . • 提出了一种动态函数调用路径编码方法，该方法可以有效的处理程序中的间接调用。与已有方法相比，本项目中提出的方法不需要通过指针分析或训练执行来获取间接调用所有的目标地址。. • 提出了一种根据程序动态执行行为调整函数调用路径编码的自适应编码方法，该方法能够有效地减小所需编码空间和降低运行时开销。与此对应，本项目中也提出了针对自适应编码方法的解码算法。. • 对多线程程序的特点进行了分析，提出了一种有效地获取多线程程序函数调用路径的方法。. • 基于SPEC CPU2006，Parsec 2.1和Cilk程序的 实验数据表明，DACCE不仅可以准确地获取所有测试用例的运行时函数调用路径信息，而且它的运行时开销也非常小(2.4%左右)。. • 共发表A类期刊/会议论文4篇，B类期刊/会议论文3篇，国内期刊论文1篇，并提交专利申请3项