Using Static Analysis to Reduce Dynamic Analysis Overhead

Dynamic analysis (instrumenting programs with code to detect and prevent errors during program execution) can be an effective approach to debugging, as well as preventing harm from being caused by malicious code. One problem with this approach is the runtime overhead introduced by the instrumentation. We define several techniques that involve using the results of static analysis to identify some cases where instrumentation can safely be removed. While we have designed the techniques with a specific dynamic analysis in mind (that used by the Runtime Type-Checking tool), the ideas may be of more general applicability.     

Rewriting executable files to measure program behavior

Inserting instrumentation code in a program is an effective technique for detecting, recording, and measuring many aspects of a program's performance. Instrumentation code can be added at any stage of the compilation process by specially-modified system tools such as a compiler or linker or by new tools from a measurement system. For several reasons, adding instrumentation code after the compilation process—by rewriting the executable file—presents fewer complications and leads to more complete measurements. This paper describes the difficulties in adding code to executable files that arose in developing the profiling and tracing tools qp and qpt. The techniques used by these tools to instrument programs on MIPS and SPARC processors are applicable in other instrumentation systems running on many processors and operating systems. In addition, many difficulties could have been avoided with minor changes to compilers and executable file formats. These changes would simplify this approach to measuring program performance and make it more generally useful.     

基于信息流的整数漏洞插装和验证

为降低整数漏洞插装验证的运行开销,提出基于信息流的整数漏洞插装方法.从限定分析对象范围的角度出发,将分析对象约减为污染信息流路径上的所有危险整数操作,以降低静态插装密度.在GCC平台上,实现了原型系统DRIVER(detect and run-time check integer-based vulnerabilities with information flow).实验结果表明,该方法具有精度高、开销低、定位精确等优点.     

A dynamic code coverage approach to maximize fault localization efficiency

Spectrum-based fault localization is amongst the most effective techniques for automatic fault localization. However, abstractions of program execution traces, one of the required inputs for this technique, require instrumentation of the software under test at a statement level of granularity in order to compute a list of potential faulty statements. This introduces a considerable overhead in the fault localization process, which can even become prohibitive in, e.g., resource constrained environments. To counter this problem, we propose a new approach, coined dynamic code coverage (DCC), aimed at reducing this instrumentation overhead. This technique, by means of using coarser instrumentation, starts by analyzing coverage traces for large components of the system under test. It then progressively increases the instrumentation detail for faulty components, until the statement level of detail is reached. To assess the validity of our proposed approach, an empirical evaluation was performed, injecting faults in six real-world software projects. The empirical evaluation demonstrates that the dynamic code coverage approach reduces the execution overhead that exists in spectrum-based fault localization, and even presents a more concise potential fault ranking to the user. We have observed execution time reductions of 27% on average and diagnostic report size reductions of 77% on average.     

一个基于Eclipse的通用Java程序插桩工具

插桩技术作为一种有效理解程序动态行为的手段,已经被广泛应用于程序分析、测试和验证中。然而,由于缺少通用的插桩工具,各种具体的应用往往需要从头开发特定的插桩程序,存在着大量的重复性工作。此外,由于在原始程序中插入了大量额外代码,致使调试过程变得更加复杂和困难。针对这些问题,提出了一个基于Eclipse的通用Java代码插桩工具,即通过规则定义匹配程序的执行点,从而定制针对各种分析、测试和验证插桩需求的支持。通过对插桩代码片段的显式/隐式切换实现其可见性管理,从而确保程序的理解和调试过程不受插桩代码影响。通过使用该工具,可以更好地将插桩技术应用于Java程序开发中。     

A specification-based approach to concurrency analysis

The behavior of a concurrent program often depends on the arbitrary interleaving of computations performed by asynchronous processes. The resulting non-determinism can lead to such phenomena as deadlock and starvation, making program development extremely difficult, and consequently making the development of tools for formal analysis highly desirable.A specification-based approach to concurrency analysis is a particularly promising way of addressing some of the difficulties inherent in concurrent program development. According to this approach, a programmer first writes a specification describing the interprocess communication behavior of a concurrent program. A set of formal analysis techniques are then applied in an effort to determine whether the specification can be fully satisfied. If the analysis is successful, target code is generated automatically that conforms to the specification.This approach has a variety of benefits. While such properties as safety and liveness are rather difficult to discern in actual code, they are actually easy to include as part of a specification. Moreover, state spaces induced by specifications tend to be smaller and more manageable than state spaces of actual code, and this leads to more effective analysis techniques. Finally, the generation of interprocess communication code from formal specifications is accomplished in a relatively straightforward manner.Research partially supported by NSF grant CCR-9109231.     

基于控制流分析的隐藏代码动态捕获方法

为获取并分析采用加壳、控制流混淆技术所产生的隐藏代码,提出一种新的隐藏代码动态捕获方法。利用静态控制流分析算法提取动态捕获点,采用动态二进制插桩技术插入监控代码,在程序的执行过程中实现隐藏代码的执行前分析。实验结果证明,该方法能够减少程序插桩点,有效获取并分析可执行程序中的隐藏代码。     

一种基于动态插桩的JavaScript反事实执行方法

目前,静态分析技术已被广泛用于JavaScript程序的安全性分析。但是由于JavaScript支持通过eval等方法在运行时动态生成代码,仅靠静态分析难以取得动态生成代码。一种可行的解决方法是通过动态运行目标程序取得动态生成代码,再对其进行静态分析。然而,动态运行目标程序只能覆盖有限的执行路径,会遗漏其他执行路径中的动态生成代码。针对这一问题,基于动态插桩实现了一个反事实执行方法。该方法通过修改JavaScript引擎,在其语法解析阶段动态插入反事实执行体,使条件不成立的分支路径和当前执行路径均能够得到执行。通过该插桩方式,即使嵌套调用eval等方法,也能在其动态生成代码中完成插桩。同时,还实现了一种按需undo方法,以消除反事实执行体中赋值操作带来的影响,且能够避免冗余操作。实验结果表明,实现的方法能够有效地扩大动态分析中执行路径的覆盖面。     

基于地址完整性检查的函数指针攻击检测

针对传统函数指针攻击检测技术无法检测面向返回编程(ROP)攻击的问题,提出了一种基于跳转地址完整性检查的新方法,在二进制代码层面能够检测多种类型的函数指针攻击。首先,通过静态分析得到函数地址信息,然后动态检查跳转目标地址是否位于合法函数区间。分析了非入口点跳转,提出一种动静结合方法检测ROP攻击。基于二进制代码插桩工具实现原型系统fpcheck,对真实攻击和正常程序进行了测试。实验结果表明fpcheck能够检测包括ROP在内的多种函数指针攻击,通过准确的检测策略,误报率显著下降,性能损失相比原始插桩仅升高10%~20%。     

逆向工程中反射植入的研究

逆向工程辅助程序理解，而动态分析是理解面向对象软件系统的一种重要手段，通过植入，才能准确提取系统运行时的信息，常见的植入方法中，植入代码和目标代码处于同一计算层次，在植入过程中，需要对目标代码进行除编译分析之外的额外语法分析。该文提出反射植入思想，将植入的软件触发器和被植入的目标系统作为两个计算层次来处理，通过反射层元对象干预编译过程，实现源代码的植入；首先详细描述反射植入核心算法及识别调用方元信息和对象标识的思路，然后在扩充开放编译器的基础上实现了全局函数和系统调用语句前植入代码的算法，最后对该植入机制进行系统的实验研究。结果表明，反射植入机制不会破坏源代码本身的执行逻辑，能正确有效地植入代码并收集到系统运行时的信息。同时，多次植入的对比数据也证明了反射植入算法的收敛性。     

Software trustworthiness 2.0—A semantic web enabled global source code analysis approach

There has been an ongoing trend toward collaborative software development using open and shared source code published in large software repositories on the Internet. While traditional source code analysis techniques perform well in single project contexts, new types of source code analysis techniques are ermerging, which focus on global source code analysis challenges. In this article, we discuss how the Semantic Web, can become an enabling technology to provide a standardized, formal, and semantic rich representations for modeling and analyzing large global source code corpora. Furthermore, inference services and other services provided by Semantic Web technologies can be used to support a variety of core source code analysis techniques, such as semantic code search, call graph construction, and clone detection. In this paper, we introduce SeCold, the first publicly available online linked data source code dataset for software engineering researchers and practitioners. Along with its dataset, SeCold also provides some Semantic Web enabled core services to support the analysis of Internet-scale source code repositories. We illustrated through several examples how this linked data combined with Semantic Web technologies can be harvested for different source code analysis tasks to support software trustworthiness. For the case studies, we combine both our linked-data set and Semantic Web enabled source code analysis services with knowledge extracted from StackOverflow, a crowdsourcing website. These case studies, we demonstrate that our approach is not only capable of crawling, processing, and scaling to traditional types of structured data (e.g., source code), but also supports emerging non-structured data sources, such as crowdsourced information (e.g., StackOverflow.com) to support a global source code analysis context.     

基于符号化执行的Fuzzing测试方法

设计并实现一种基于符号化执行的Fuzzing测试方法。通过代码插装,在程序执行过程中收集路径约束条件,依据一定的路径遍历算法生成新路径约束条件并进行求解,构造可以引导程序向新路径执行的输入测试数据。提出一种改进的污点分析机制,对路径约束条件进行简化,提高了代码覆盖率和漏洞检测的效率。     

Integrated moving target defense and control reconfiguration for securing Cyber-Physical systems

With the increasingly connected nature of Cyber-Physical Systems (CPS), new attack vectors are emerging that were previously not considered in the design process. Specifically, autonomous vehicles are one of the most at risk CPS applications, including challenges such as a large amount of legacy software, non-trusted third party applications, and remote communication interfaces. With zero day vulnerabilities constantly being discovered, an attacker can exploit such vulnerabilities to inject malicious code or even leverage existing legitimate code to take over the cyber part of a CPS. Due to the tightly coupled nature of CPS, this can lead to altering physical behavior in an undesirable or devastating manner. Therefore, it is no longer effective to reactively harden systems, but a more proactive approach must be taken. Moving target defense (MTD) techniques such as instruction set randomization (ISR), and address space randomization (ASR) have been shown to be effective against code injection and code reuse attacks. However, these MTD techniques can result in control system crashing which is unacceptable in CPS applications since such crashing may cause catastrophic consequences. Therefore, it is crucial for MTD techniques to be complemented by control reconfiguration to maintain system availability in the event of a cyber-attack. This paper addresses the problem of maintaining system and security properties of a CPS under attack by integrating moving target defense techniques, as well as detection, and recovery mechanisms to ensure safe, reliable, and predictable system operation. Specifically, we consider the problem of detecting code injection as well as code reuse attacks, and reconfiguring fast enough to ensure the safety and stability of autonomous vehicle controllers are maintained. By using MTD such as ISR, and ASR, our approach provides the advantage of preventing attackers from obtaining the reconnaissance knowledge necessary to perform code injection and code reuse attacks, making sure attackers can’t find vulnerabilities in the first place. Our system implementation includes a combination of runtime MTD utilizing AES 256 ISR and fine grained ASR, as well as control management that utilizes attack detection, and reconfiguration capabilities. We evaluate the developed security architecture in an autonomous vehicle case study, utilizing a custom developed hardware-in-the-loop testbed.     

Toward the Reverse Engineering of UML Sequence Diagrams for Distributed Java Software

This paper proposes a methodology and instrumentation infrastructure toward the reverse engineering of UML (Unified Modeling Language) sequence diagrams from dynamic analysis. One motivation is, of course, to help people understand the behavior of systems with no (complete) documentation. However, such reverse-engineered dynamic models can also be used for quality assurance purposes. They can, for example, be compared with design sequence diagrams and the conformance of the implementation to the design can thus be verified. Furthermore, discrepancies can also suggest failures in meeting the specifications. Due to size constraints, this paper focuses on the distribution aspects of the methodology we propose. We formally define our approach using metamodels and consistency rules. The instrumentation is based on aspect-oriented programming in order to alleviate the effort overhead usually associated with source code instrumentation. A case study is discussed to demonstrate the applicability of the approach on a concrete example     

Comprehensive aspect weaving for Java

Aspect-oriented programming (AOP) has been successfully applied to application code thanks to techniques such as Java bytecode instrumentation. Unfortunately, with existing AOP frameworks for Java such as AspectJ, aspects cannot be woven into the standard Java class library. This restriction is particularly unfortunate for aspects that would benefit from comprehensive aspect weaving with complete method coverage, such as profiling or debugging aspects. In this article we present MAJOR, a new tool for comprehensive aspect weaving, which ensures that aspects are woven into all classes loaded in a Java Virtual Machine, including those in the standard Java class library. MAJOR includes the pluggable module CARAJillo, which supports efficient access to a complete and customizable calling context representation. We validate our approach with three case studies. Firstly, we weave existing profiling aspects with MAJOR which otherwise would generate incomplete profiles. Secondly, we introduce an aspect for memory leak detection that also benefits from comprehensive weaving. Thirdly, we present an aspect subsuming the functionality of ReCrash, an existing tool based on low-level bytecode instrumentation techniques that generates unit tests to reproduce program failures. Our aspect-based tools are concisely implemented in a few lines of code, and leverage MAJOR and CARAJillo for comprehensive aspect weaving and for efficient access to calling context information.     

软件测试中代码分析与插装技术的研究

软件测试作为软件工程的重要组成部分对提高软件质量和可靠性起到了不可忽视的作用。软件白盒测试自动化工具WBoxTool中对标准C/C++程序进行了可视化的插装和监视,收集程序动态运行信息,并进行可靠的测试分析。该文介绍了在工具WBoxTool中使用的代码分析和插装测试技术,并给出插装测试方法的一些实例应用和分析。     

采用C＋＋代码插装的实时软件内存错误分析

在航天领域中,安全关键的大型实时软件系统往往直接影响到任务成败,一般难以全面检测、分析或避免内存泄漏等常见内存错误。定义了实时软件的12种典型内存故障模式,提出了一种基于C＋＋代码插装的实时软件内存错误快速分析方法。该方法通过对C＋＋源代码进行静态分析,获取指针变量相关信息;通过C＋＋代码插装和运行不同测试用例,实时收集统计C＋＋指针对象的分配、释放、赋值、c-use和p-use使用情况,结合实时软件的典型内存故障模式进行分析,并自动生成详情报告。应用案例表明,该方法能够高效快捷地发现实时软件潜在的典型内存错误,从而有效提高软件质量。     

A policy-based approach for strong mobility of composed Web services

This paper presents a flexible, portable, and transparent solution for strong mobility of composed Web services relying on policy-oriented techniques. The proposed approach provides a checkpoint solution based on automatic code instrumentation using correct source code transformation rules. This checkpoint technique permits to save the execution state of a mobile orchestration process as well as the execution states of its orchestrated partners. Thus, after migration, only non-executed codes will be resumed. In addition, our approach enables dynamic adaptation of the employed checkpointing and mobility techniques using aspects. For that, we use policies allowing dynamic selection of the used checkpointing and mobility techniques according to the execution context. Moreover, the proposed solution includes a module allowing the determination of the checkpointing interval satisfying QoS requirements. Experimentations show the efficiency of the proposed solution.