一种改进的静态程序切片算法

提出了一种改进的静态程序切片算法,并应用到软件逆向工程中。在处理目标程序的过程间调用时,通过建立参数影射关系表,将过程间调用转换为过程内调用,简化了建立程序依赖图的复杂度;在归纳分析目标程序变量类型的基础上,给出了代数运算法则,对程序中的线性运算代码进行等价变换,缩减了切片程序的规模。最后通过具体的切片实例,证明了改进算法的有效性。     

一种基于代码静态分析的缓冲区溢出检测算法

缓冲区溢出目前已成为最常见的软件安全漏洞之一,从源代码形式来看,常见的缓冲区溢出漏洞主要有两种类型:数据拷贝和格式化字符串造成的缓冲区溢出.分析了常见缓冲区溢出漏洞发生的原因,给出了格式化字符串存储长度的计算方法,介绍了一种基于源代码静态分析的缓冲区溢出检测算法,该算法首先对源代码进行建模,构造其抽象语法树、符号表、控制流图、函数调用图,在此基础上运用区间运算技术来分析和计算程序变量及表达式的取值范围,并在函数间分析中引入函数摘要来代替实际的函数调用.最后使用该方法对开源软件项目进行检测,结果表明该方法能够有效地、精确地检测缓冲区溢出.     

面向物联网设备安全的多层次内核访问控制方法

物联网设备受能耗、计算能力等因素限制, 通常采用轻量化的操作系统以及精简化的安全保护机制, 导致物联网设备的操作系统安全保护能力不足, 更容易被用户态程序攻破。为了增强操作系统的隔离能力, 现有的安全保护方法通常限制应用程序可访问的系统调用种类, 使其仅能访问运行所必须的系统调用, 从而缩小操作系统的攻击面。然而, 现有的动态或者静态程序分析方法无法准确获取目标程序运行所依赖的系统调用。动态跟踪方法通过跟踪程序执行过程中触发的系统调用, 仅能获取程序依赖系统调用的子集, 以此作为依据的访问控制可能会影响程序的正常执行。而静态分析方法通常构造程序及其依赖库的控制流图并分析其可达的系统调用, 然而由于静态分析无法精准构建控制流图, 仅能获取目标程序依赖系统调用的超集, 会在访问控制中引入多余的系统调用, 造成操作系统攻击面依然较大。针对现有系统调用访问控制面临的可用性以及精准度问题, 研究多层次的内核访问控制方法, 在现有系统调用访问控制的基础上, 引入了动态链接库的访问控制, 并提出了多层联动的动态安全分析机制, 以动态分析的方法排除由于静态分析不准确引入的额外系统调用, 从而进一步缩小物联网系统的攻击面, 提升物联网设备的隔离能力与安全性。实验结果表明, 相比于现有内核访问控制方法, 本文提出的方法能够抵御更多漏洞而且引入的实时负载更低。     

基于多分支语句的控制流迷惑技术

控制流速惑是代码迷惑的一个重要方面．程序控制流分为过程内控制流及过程间控制流．本文提出了一种基于switch_case语句的控制流迷惑技术；首先给出一种基于switch语句的程序变换方法，使得过程内的控制流关系变得复杂，同时利用switch语句对整个程序中的函数进行重新定义，从而迷惑程序中的函数调用关系，以达到迷惑过程间控制流信息的目的．最后表文定性地分析了这种代码迷惑技术的性能．     

面向SIMD的数组重组和对齐优化

随着多媒体应用的普及,越来越多的处理器集成了SIMD扩展,但是非连续或者非对齐访存会阻碍程序的向量化或者造成性能损失。针对实际应用中出现的数组引用不连续的情况,提出了一种数学模型,用以刻画数组的访存模式和数据重组方案,以判断这些数组引用是否可以通过数组转置的方法满足连续性要求;并采用过程间数组填充、循环剥离和基于SLP的向量化代码生成方法等进行对齐优化。最后基于SPEC2000测试集对该算法进行了测试,结果表明,该方法可以有效地提升向量化程序的执行效率。     

静动态结合的恶意Android应用自动检测技术

随着移动互联网的快速发展,移动终端及移动应用在人们日常生活中越来越重要,与此同时,恶意移动应用给网络和信息安全带来了严峻的挑战。Android平台由于其开放性和应用市场审查机制不够完善,使其成为了移动互联网时代恶意应用的主要传播平台。现有的恶意应用检测方法主要有静态分析和动态测试两种。一般而言,静态分析方法代码覆盖率高、时间开销小,但存在误报率较高的问题;而动态测试准确度较高,但需要实际运行应用,所需的时间和计算资源开销较大。针对上述情况,本文基于静动态结合的方法,自动检测恶意Android应用。首先,使用静态分析技术获取应用API的调用情况来判定其是否为疑似恶意应用,特别是可有效检测试图通过反射机制调用API躲避静态分析的恶意应用;然后,根据疑似恶意应用UI控件的可疑度进行有针对性的动态测试,来自动确认疑似恶意应用中是否存在恶意行为。基于此方法,我们实现了原型检测工具框架,并针对吸费短信类恶意行为,对由465个恶意应用和1085个正常应用组成的数据集进行了对比实验。实验结果表明,该方法在提高恶意应用检测效率的同时,有效地降低了误报率。     

Function call interception techniques

Function call interception (FCI), or method call interception (MCI) in the object‐oriented programming domain, is a technique of intercepting function calls at program runtime. Without directly modifying the original code, FCI enables to undertake certain operations before and/or after the called function or even to replace the intercepted call. Thanks to this capability, FCI has been typically used to profile programs, where functions of interest are dynamically intercepted by instrumentation code so that the execution control is transferred to an external module that performs execution time measurement or logging operations. In addition, FCI allows for manipulating the runtime behavior of program components at the fine‐grained function level, which can be useful in changing an application's original behavior at runtime to meet certain execution requirements such as maintaining performance characteristics for different input problem sets. Due to this capability, however, some FCI techniques can be used as a basis of many security exploits for vulnerable systems. In this paper, we survey a variety of FCI techniques and tools along with their applications to diverse areas in the computing and software domains. We describe static and dynamic FCI techniques at large and discuss the strengths and weaknesses of different implementations in this category. In addition, we also discuss aspect‐oriented programming implementation techniques for intercepting method calls.     

基于Define-Use图的MPI通信求解算法

针对分布存储计算机系统并行编译过程中,为维持数据一致性而产生冗余通信的问题,提出一种优化的通信求解算法。该算法基于依赖关系分析和过程间数据流分析,通过遍历Define-Use图,获得更精确的通信数据,消除过程调用时产生的冗余通信。实验结果表 明,将算法所得结果作为后端生成MPI通信代码的依据,可以有效减少通信量,加速比接近手工MPI并行程序。     

基于CFG的函数调用关系静态分析方法

函数调用关系能够反映软件系统中函数间的依赖关系,完整的函数调用关系可以更好地辅助程序验证和死锁分析,提升验证和分析的完备性.现有静态分析函数调用关系的方法不能准确分析函数指针和虚函数的调用,影响了其分析结果的准确性.针对这一问题本文提出了一种基于控制流图(Control Flow Graph, CFG)的函数调用关系静态分析方法,该方法首先使用GCC插件静态获取源代码中的类型和函数CFG等信息并构建分析路径,然后采用本文提出的模拟仿真算法分析程序中的语句,并解析函数指针和虚函数的调用,最后基于分析结果生成完整的函数调用关系.实验结果表明,该方法能够很好地支持对函数指针和虚函数的处理,提升了分析结果的准确性.     

一种基于类的Java多线程程序数据竞争静态检测算法

多线程并发程序的广泛使用引发了更多的数据竞争问题,竞争检测对于提高软件质量具有重要意义。将竞争静态检测和静态切片分析结合起来,提出了一种基于类的Java数据竞争静态检测算法,该算法利用函数调用层次获得函数调用链,对类域进行分析,找出可能数据竞争,通过静态切片缩小程序分析范围,并结合数据竞争的必要条件,去掉不可能数据竞争。实例表明,该算法可用于指导修复程序中的竞争缺陷。     

结合静态分析与动态符号执行的软件漏洞检测方法

动态符号执行是近年来新兴的一种软件漏洞检测方法,它可以为目标程序的不同执行路径自动生成测试用例,从而获得较高的测试代码覆盖率。然而,程序的执行路径很多,且大部分路径都是漏洞无关的,通常那些包含危险函数调用的路径更有可能通向漏洞。提出一种基于静态分析的有导动态符号执行方法,并实现了一个工具原型SAGDSE。该方法通过静态分析识别目标程序中调用危险函数的指令地址,在动态符号执行过程中遇到这些指令地址时收集危险路径约束,再通过约束求解生成走危险路径的测试用例,这些测试用例将更可能触发程序漏洞。实验结果表明了该方法的有效性。     

带控制流的静态函数调用分析方法

提出一种带有控制流的静态函数调用分析的方法,通过建立模型,对源程序进行静态分析,得到程序中的控制流信息和函数调用信息。和已有的静态函数调用关系图分析工具calltree和Source Insight相比,该方法生成的函数调用流图不仅能展现函数间的调用次序,还可以了解程序设计的逻辑复杂度,有助于代码阅读和分析人员更快更好地理解程序结构以及设计流程,并为分析程序控制条件、设计路径覆盖测试用例和进行程序优化奠定基础。     

Java程序中数组越界和空指针错误的静态分析

介绍了静态分析的相关背景知识,对Java程序中数组越界和空指针错误的常见表现形式进行了归类,并通过实验评估了现有的Java静态分析工具功能,指出了其在跨过程分析中的不足,并对如何改进进行了讨论。     

Optimizing the stack size of recursive functions

For memory constrained environments, optimization for program size is often as important as, if not more important than, optimization for execution speed. Commonly, compilers try to reduce the code segment but neglect the stack segment, although the stack can significantly grow during the execution of recursive functions because a separate activation record is required for each recursive call.If a formal parameter or local variable is dead at all recursive calls, then it can be declared global so that only one instance exists independent of the recursion depth. We found that in 70% of our benchmark functions, it is possible to reduce the stack size by declaring formal parameters and local variables global. Often, live ranges of formal parameters and local variables can be split at recursive calls through program transformations. These splitting transformations allowed us to further optimize the stack size of all our benchmark functions. If all formal parameters and local variables can be declared global, then such functions may be transformable into iterations. This was possible for all such benchmark functions.     

二进制代码中函数混淆调用的识别

函数调用相关信息识别是二进制代码静态分析的基础,也是恶意代码分析的重要线索。二进制代码混淆技术通过对函数调用指令call、参数传递过程和调用返回过程的混淆来隐藏代码中函数的信息。这大大增加了程序逆向分析的难度,此技术被广泛应用在变形和多态病毒中,使其逃脱杀毒软件的查杀。论文给出了一种静态分析方法,引入了抽象栈图的概念,给出了其构造算法,利用它能够有效识别出代码中对函数调用的混淆。     

递归子程序的依赖性分析及其应用

程序依赖性是一种重要的程序分析、理解与维护方法,广泛应用于软件工程及软件逆向工程的各个方面,但递归子程序间的依赖分析一直是依赖性分析中的难点。为此,该文提出了一种新的递归子程序间的依赖性分析方法,它首先分析子程序内部的各种依赖关系;然后,结合子程序调用图分析子程序参数间的依赖关系;最后,通过模拟递归子程序的执行过程来分析它们之间的依赖关系。利用该文提供的方法可得到比较精确的递归子程序间的依赖关系。     

Ripple: Reflection analysis for Android apps in incomplete information environments

Reflection poses grave problems for static security analysis, despite its widespread use in Android apps. In general, string inference has been mainly used to handle reflection, resulting in significantly missed security vulnerabilities. In this work, we bring forward the ubiquity of incomplete information environments (IIEs) for Android apps, where some critical dataflows are missing during static analysis and the need for resolving reflective calls under IIEs. We present Ripple , the first IIE‐aware static reflection analysis for Android apps that resolves reflective calls more soundly than string inference. Validation with 17 popular Android apps from Google Play demonstrates the effectiveness of Ripple in discovering reflective targets with a low false positive rate (due to its trade‐off made among soundness, precision, and scalability). As a result, Ripple enables FlowDroid , a taint analysis for Android apps, to find hundreds of sensitive data leakages that would otherwise be missed. As a fundamental analysis, Ripple will be valuable for many security analysis clients, since more program behaviors can now be analyzed under IIEs.     

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.     

Deciding branching time properties for asynchronous programs

Asynchronous programming is a paradigm that supports asynchronous function calls in addition to synchronous function calls. Programs in such a setting can be modeled by automata with counters that keep track of the number of pending asynchronous calls for each function, as well as a call stack for synchronous recursive computation. These programs have the restriction that an asynchronous call is processed only when the call stack is empty. The decidability of the control state reachability problem for such systems was recently established. In this paper, we consider the problems of checking other branching time properties for such systems. Specifically we consider the following problems — termination, which asks if there is an infinite (non-terminating) computation exhibited by the system; control state maintainability, which asks if there is a maximal execution of the system, where all the state visited lie in some “good” set; whether the system can be simulated by a given finite state system; and whether the system can simulate a given finite state system. We present decision algorithms for all these problems.     

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.