论运行踪迹和任务逻辑关系

第一章绪论

随着计算机技术和互联网应用技术的高速发展，形色各异的应用软件已经深入到政治、经济、军事、文化、科技、教育、卫生等社会的各行各业，以及人民群众日常生活的方方面面。然而，任何软件产品都不可能完全保证没有任何缺陷或者漏洞，而且在软件开发过程中，软件需求也不可能精确地描述用户的需求，用户的需求也是变化的。上述原因导致开发出来的软件需要不断地进行修改，功能扩充和打补丁等之类的操作，这在我们使用软件的过程中是随处可见。此外，对于一些规模庞大的系统，在软件设计与实现的过程中不可避免地会产生错误，从而使系统表现与预期的行为有差异。软件运行错误的根本原因通常隐含在复杂的应用逻辑之下，而且大型软件通常都是分工协作的产物，找到这些错误通常需要花费很长时间。软件开发商为了保护自己的利益，通常软件都是以执行码的形式发布，用户不可能获得软件的源码，这些复杂的系统对于用户來说就像一个"黑盒"，使得他们面对系统产生的问题无从下手。

1.1.研究背景及意义

理解软件的运行时行为对于软件开发人员是至关重要的，其可以帮助他们验证软件的设计、解决软件实现时产生的错误、发现软件逻辑与性能的问题。然而，随着软件系统的益庞大，软件设计非常复杂，而且运行时的行为多种多样，因此即使对软件的直接开发人员来说，充分理解系统逻辑也不是一件容易的事情。再者，软件通常分为不同的部分，由不同组的程序员共同开发，并且在日后随着用户的需求改变和软件性能需求不停地演变至新的版本。进一歩说，应用软件通常会使用分层的设计模式，不同层次的模块共同配合处理用户的请求。上层模块中的某个函数会由下层模块的多个函数一起完成，其完成方式可能是顺序的，也可能是并行的，跨越多个机器、进程与线程。以上这些状况都对开发人员理解系统运行时行为造成巨大的障碍。因此，研究系统任务行为的逻辑关系，为了解系统的可信度及性能，系统设计及系统优化提供帮助，具有深刻的意义。..................
....................

第二章相关工作

本章主要描述本文涉及的相关研究工作与理论。首先介绍代码插装技术，这是一个了解软件运行行为的强大机制，通常分为静态插装和动态插装，本章分别介绍了两种插装技术。接着介绍了几个典型的踪迹分析方法。然后描述了时序逻辑的基本思想，并分别介绍了线性时序逻辑和计算树逻辑，本文最后将使用计算树逻辑对任务状态进行描述。最后是本章小结。

2.1.代码插装技术

代码插装是通过在程序中插入新的代码或修改现有代码来修正程序执行过程的行为技术。代码插装可应用于源代码和编译后生成的二进制码。当其应用于后者的情况时，代码可以在程序执行前进行静态插装，也可动态地应用与程序执行时。代码插装是了解和修改程序运行行为的一个强大的机制。它广泛适用于各个领域，包括软件调试，性能评估，软件可视化，软件访问控制，分布式计算等。代码插装是一种在程序中插入额外代码去从而获取程序运行信息的技术。它可以执行于软件执行的四个阶段：源代码阶段，编译阶段，链接阶段和运行阶段。前三个阶段发生于程序运行之前，我们称之为"静态插装"；最后一个阶段处于程序运行时，称之为"动态插装"。代码插装技术使得获取程序运行时的行为信息称为可能，为调试和测试人员提供了快速有效的了解程序的手段。
由于系统调用信息可以在一定程度上反映出程序的运行情况，因此可以使用系统调用信息来对程序任务关系进行分析。

2.1.1.静态代码插装

静态代码插装实施于代码运行之前，是面向代码级的插装。目前静态代码插桩技术主要针对源代码插桩和二进制码插桩。
1)源代码插装技术
顾名思义，源代码插装技术主要是指在源代码中进行代码插入。它主要包括两种形式的插装，一种是将代码插装到源代码之后再进行编译和链接生成目标代码，需要开发一个专门的词法、语法分析器来进行程序插装；另一种形式是在程序编译的时候，通过编译器对程序进行代码插装，不需要修改源程序代码，效率较高''。
2)请求解析器
请求解析器负责从交错的事件円志中提取独立的请求。通过确定哪些事件涉及到某个特定的请求，解析器建立一个请求的说明以获取每个阶段中事件的控制流和资源使用情况。解析器认为依赖一个事件模式來形容特定应用程序事件关系。例如，发生在同一线程上属于同一请求的事件序列，在事件模式上描述将会通过指定线程ID来关联这些事件。线程可以对任意数量的不同请求标注相同的事件序列。
3)建模
Magpie使用因果关系注释，为每个请求生成一个规范化的版本。然后使用聚类算法对规范化的请求进行分类，主要考虑两个事件的顺序和资源消耗情况。

2.2.5.自动推断复杂系统层次结构任务模型

该方法是有清华大学高崇南等人提出來的一种不需要人工帮助而自动推断系统层次结构的方法，并实现了推断工具ScalpeF人该方法使用R2的插装技术透明地获取系统运行过程的应用层函数和系统函数的调用信息，以此为trace,自下而上地推断系统层次结构。.................
................
第三章算法分析与形式描述..............22
3.1.推断规则与分析.........................22
3.2.踪迹分析算法....................23
3.3.1.算法描述.............................24
3.3.2.算法复杂度分析.................28
3.3.任务逻辑关系描述..............29
3.4.本章小结.............................30
第四章结果验证.......................................31
4.1.Windows系统调用机制...................31
4.2.Auto Debug软件实现方法.........32
4.3.踪迹获取及分析..........................35
4.3.1.踪迹获取...........................35
4.3.2.踪迹分析...........................38
4.3.3.任务逻辑描述...................39
4.4.本章小结............................41

总结与展望

随着软件系统在科技高速发展的时代得到广泛的应用，软件分析成为热门的研究课题。对软件结构及逻辑的研究，有助于人们对软件进行二次丌发，优化或者性能分析。对软件结构的分析己经有许多方法，考虑到软件运行时在用户态和内核态的交互，本文提出使用系统调用踪迹对软件任务的逻辑关系进行分析。

1.研究工作总结

本文主要研究基于系统调用踪迹的软件任务逻辑关系。通过使用代码插装技术动态获取软件运行过程中的系统调用信息。然后以此信息为基础数据，提取任务的原子操作以及任务的逻辑层次。本文提出的算法经过实验验证，表明该算法能够准确表示出软件某个任务的逻辑关系，并使用计算树逻辑在Kripke迁移系统上描述任务状态的变迁情况。
本文的主要工作有：

1.1综述了国内外对踪迹研究的现状，分析了几种踪迹分析的方法并对其进行比较，介绍了踪迹分析的应用领域；

介绍了获取踪迹的方法一一代码插装技术，详细介绍了动态代码插装技术；
提出了对踪迹分析的规则，并详细描述了分析踪迹数据和提取任务层次结构的算法。然后提出使用计算树逻辑（CTL)在Kripke迁移系统上描述FTP下载文件的任务状态迁移情况；
介绍Auto Debug的实现原理及Windows系统调用机制原理。然后采用FTP客户端对服务器文件下载作为实例，使用Auto Debug获取软件系统调用踪迹，作为分析任务模型的基础数据。最后使用踪迹分析算法和提取任务层次结构算法对获取的基础数据进行分析。