构造面向对象系统依赖图技术研究

本文分析了现有面向对象图形表示方案存在的问题,在此基础之上,提出了基于波动效应分析构造面向对象系统依赖图的方法,通过引入波动效应分析,来完善面向对象程序的语义和减小构图的复杂性,在波动效应分析的基础之上,构造类图、改造面向过程的系统依赖图,结合两个图来描述面向对象程序。通过类图描述不同类之间的关联关系和类的内部定义,在类图中表达过程依赖,改造面向过程的系统依赖图用于表达控制依赖和数据依赖。文中给出了计算波动效应和构造系统依赖图的算法描述。     

串行程序的任务DAG图构造算法

任务DAG图是刻画程序中各任务间依赖关系的一种手段,DAG图上除了标有任务间的依赖关系,还记录了各任务的计算量和任务之间的通信量,这些信息共同构成了任务调度的依据,国内外有许多基于任务DAG图的调度算法研究,但通过分析串行程序的相关性来构造任务DAG图的研究却不多见.分析了串行程序中存在的数据相关性和控制相关性,就程序中的顺序,分支,循环三种基本结构进行分别讨论,提出了一种串行程序任务DAG图的构造算法.     

分布式系统中求解RPC最大响应时间的一种基于状态图的 …

远程过程调用ＲＰＣ（Ｒｅｍｏｔｅ Ｐｒｏｃｅｄｕｒｅ Ｃａｌｌ）是分布式系统中机间通讯的一种重要手段,分布式系统的性能很大程度上依赖于ＲＰＣ响应时间。使用回归模型和队列模型可对ＲＰＣ响应时间进行分析。但是回归模型不能很好地反映ＲＰＣ设计变化对响应时间的影响,而队列模型又要求 较多的假设。针对以上模型的不足,本文提出用有穷状态迁移图构造ＲＰＣ模型,并给出了一个基于状态图的求解ＲＰＣ最大响应时间的算法     

分布式系统中求解RPC最大响应时间的一种基于状态图的算法

远程过程调用 ＲＰＣ （Ｒｅｍ ｏｔｅ Ｐｒｏｃｅｄｕｒｅ Ｃａｌｌ）是分布式系统中机间通讯的一种重要手段．分布式系统的性能很大程度上依赖于ＲＰＣ响应时间．使用回归模型和队列模型可对ＲＰＣ响应时间进行分析．但是回归模型不能很好地反映ＲＰＣ设计变化对响应时间的影响,而队列模型又要求对系统作较多的假设．针对以上模型的不足,本文提出用有穷状态迁移图构造ＲＰＣ模型,并给出了一个基于状态图的求解ＲＰＣ 最大响应时间的算法．经过证明和时间复杂性分析,该算法是正确而有效的     

构造串行程序对应的并行任务(DAG)图

目前在并行计算研究领域中很大一部分工作是将串行程序并行化,如何发掘串行程序中存在的并行性,一个好的方法就是构造其对应的并行任务(DAG)图,对并行任务图的分析,调度和最终实现并行计算的工作已经有很多人做过,但是由串行程序构造DAG图的工作相对很少。论文分析了串行程序中存在的依赖关系,并以此为依据,提出了一种由现有的串行程序或者串行解决方案构造对应的并行任务(DAG)图的算法。     

极大完全子图在管理决策中的应用

本文讨论了将一类管理事务问题抽象为求解极大完全子图问题，并且给出了算法及程序。     

一种基于通知波动效应的面向方面系统依赖图构造方法

为更好地分析面向方面程序中的控制依赖关系和数据依赖关系,需要对面向方面程序构造系统依赖图。本文针对面向方面程序的结构和机制,考虑通知优先级对程序依赖关系的影响,提出通知波动效应图(AFG)及其生成算法,从而构造基于通知波动效应的面向方面系统依赖图(AOSDG)。此方法构造的系统依赖图能够更准确地表示面向方面程序中的依赖关系,且构造成本相对较小,可应用于面向方面程序切片。     

程序转换中的中间表示

程序的中间表示是一种与源程序等价的程序的可分析形式。本文根据程序转换、划分与优化的需要、对文献[1]提出的程序PDG图进行了改进和扩充,在此基础上提出了系统相关图的概念,并详细地讨论了它们的构造算法。     

面向方面程序的调用图生成算法

调用图(call graph)分析是进行程序分析、程序理解、软件测试和软件维护的重要基础.目前已提出的调用图生成算法多数是针对面向对象编程;而面向方面编程作为面向对象编程的扩展,还没有比较良好的调用图生成算法.为此,分析了既有的面向对象程序调用图生成算法,讨论了面向方面程序语言(AspectJ为例)的特殊语言元素及其对生成的调用图的影响,从而构筑了面向方面程序调用图的生成算法.     

一种精确的调用图生成技术

调用图是过程间分析和程度自动并行化的基础。生成精确调用图可以进一步开发程序的并行性。此文针对Ｆｏｒｔｒａｎ程序，提出了一项完全消除哑过程，产生精确调用图的技术与相应的算法。该算法已在面向ＭＰＰ Ｆｏｒｔｒａｎ的程序自动并行化工具中实现。     

Precise Call Graphs for C Programs with Function Pointers

The use of pointers presents serious problems for software productivity tools for software understanding, restructuring, and testing. Pointers enable indirect memory accesses through pointer dereferences, as well as indirect procedure calls (e.g., through function pointers in C). Such indirect accesses and calls can be disambiguated with pointer analysis. In this paper we evaluate the precision of one specific pointer analysis (the FA pointer analysis by Zhang et al.) for the purposes of call graph construction for C programs with function pointers. The analysis is incorporated in a production-strength code-browsing tool from Siemens Corporate Research in which the program call graph is used as a primary tool for code understanding.The FA pointer analysis uses an inexpensive, almost-linear, flow- and context-insensitive algorithm. To measure analysis precision, we compare the call graph constructed by this analysis with the most precise call graph obtainable by a large category of existing pointer analyses. Surprisingly, for all our data programs the FA analysis achieves the best possible precision. This result indicates that for the purposes of call graph construction, inexpensive pointer analyses may provide precision comparable to the precision of expensive pointer analyses.     

Constructing the Call Graph of a Program

The proliferation of large software systems written in high level programming languages insures the utility of analysis programs which examine interprocedural communications. Often these analysis programs need to reduce the dynamic relations between procedures to a static data representation. This paper presents one such representation, a directed, acyclic graph named the call graph of a program. We delineate the programs representable by an acyclic call graph and present an algorithm for constructing it using the property that its nodes may be linearly ordered. We prove the correctness of the algorithm and discuss the results obtained from an implementation of the algorithm in the PFORT Verifier [1].     

Trin-Trin: Who’s Calling? A Pin-Based Dynamic Call Graph Extraction Framework

Multi-core based systems are ubiquitous in data centers. Efficient exploitation of hardware parallelism supported by such systems is imperative on multiple fronts: minimizing latency and power consumption and maximizing throughput. This in turn calls for advanced program analysis and optimization. Call graphs have been long used to this end. Although several static call graph extraction techniques have been proposed in the past, these techniques cannot be applied to analyze programs already running in production. Likewise, the existing dynamic call graph extraction tools have limited use in production owing to, say (but not limited to), lack of support for capturing wall clock time spent in functions of a given program and lack of means to analyze the call graph information captured at run time. In this paper, we present a Pin-based dynamic call graph extraction framework called Trin-Trin. The framework enables extraction of complete, precise and dynamic call graphs. Additionally, the framework can be used seamlessly with already running applications. Furthermore, an analytics engine is provided to facilitate advanced program analysis, e.g., different multithreading context(s) of any function can be extracted in a demand-driven fashion. We evaluate the overhead of Trin-Trin using several Unix utilities, applications from the industry-standard SPEC CINT2006, CFP2006 benchmark suite and Yahoo! properties. Additionally, we present a case study to illustrate how Trin-Trin can be used to analyze performance bottlenecks and performance regressions.     

SymPas: Symbolic Program Slicing

Program slicing is a technique for simplifying programs by focusing on selected aspects of their behavior.Current mainstream static slicing methods operate on dependence graph PDG (program dependence graph) or SDG (system dependence graph),but these friendly graph representations may be a bit expensive for some users.In this paper we attempt to study a light-weight approach of static program slicing,called Symbolic Program Slicing (SymPas),which works as a dataflow analysis on LLVM (low-level virtual machine).In our SymPas approach,slices are stored in symbolic forms,not in procedures being re-analyzed (cf.procedure summaries).Instead of re-analyzing a procedure multiple times to find its slices for each callling context,we calculate a single symbolic slice which can be instantiated at call sites avoiding re-analysis;SymPas is implemented with LLVM to perform slicing on LLVM intermediate representation (IR).For comparison,we systematically adapt IFDS (interprocedural finite distributive subset) analysis and the SDG-based slicing method (SDG-IFDS) to statically slice IR programs.Evaluated on open-source and benchmark programs,our backward SymPas shows a factor-of-6 reduction in time cost and a factor-of-4 reduction in space cost,compared with backward SDG-IFDS,thus being more efficient.In addition,the result shows that after studying slices from 66 programs,ranging up to 336800 IR instructions in size,SymPas is highly size-scalable.     

基于程序分析的自动化漏洞挖掘工具的研究

研究和设计了一个基于程序分析的源代码漏洞分析与检测工具框架,框架中的各个模块如控制流分析(控制流图的构建、函数调用图的实现及过程内分析与过程间分析等)、数据流分析(求定义引用链、污染数据传播的设计、指针别名分析)、结构分析器、安全调度器、规则构建器,本文主要对代码分析的两个阶段进行了较为详细的介绍,同时对主要采取的过程内和过程间分析算法做了说明。     

基于混合分析的Java反序列化利用链挖掘方法

Java反序列化漏洞已经成为当下Java应用安全的常见威胁,其中能够找到反序列化利用链是该类型漏洞能否利用的关键.由于Java应用及依赖库的代码空间大和Java本身多态的问题,人工分析Java反序列化利用链,需消耗大量的时间和精力,且高度依赖分析人员的经验知识.因此,研究如何高效且准确地自动化挖掘反序列化利用链至关重要...     

嵌入式微处理器保护方式下高特权级系统调用的研究

设计拥有我国自主版权的微处理器有着重大意义。高特权级系统调用算法及高特权级系统调用测试单元ＰＣＵ是拥有保护机制微处理器的重要组成部分,文中探讨了保护方式下高特权级系统调用的数据结构、定义,给出了高特权级系统调用算法,提出了高特权级系统调用测试单元ＰＣＵ的细胞群结构,并指出细胞是高特权级系统调用测试单元ＰＣＵ的基本测试单位。细胞群结构概念的提出解决了微处理器保护测试单元结构设计的难题,使设计拥有自主     

IA-64过程调用的逆向恢复技术

本文给出了对于IA-64体系结构可执行程序逆向恢复中过程识别和抽象的技术实现方法。采用自动机理论与模板匹配相结合的方法解决IA-64体系结构模板中不确定指令的识别问题。实现了基于数据流分析对过程调用的参数和返回值进行恢复的算法。有效地完成了过程调用的二进制代码向与硬件无关中间语言代码转换的恢复工作。