Platform‐independent profiling in a virtual execution environment

Virtual execution environments, such as the Java virtual machine, promote platform‐independent software development. However, when it comes to analyzing algorithm complexity and performance bottlenecks, available tools focus on platform‐specific metrics, such as the CPU time consumption on a particular system. Other drawbacks of many prevailing profiling tools are high overhead, significant measurement perturbation, as well as reduced portability of profiling tools, which are often implemented in platform‐dependent native code. This article presents a novel profiling approach, which is entirely based on program transformation techniques, in order to build a profiling data structure that provides calling‐context‐sensitive program execution statistics. We explore the use of platform‐independent profiling metrics in order to make the instrumentation entirely portable and to generate reproducible profiles. We implemented these ideas within a Java‐based profiling tool called JP. A significant novelty is that this tool achieves complete bytecode coverage by statically instrumenting the core runtime libraries and dynamically instrumenting the rest of the code. JP provides a small and flexible API to write customized profiling agents in pure Java, which are periodically activated to process the collected profiling information. Performance measurements point out that, despite the presence of dynamic instrumentation, JP causes significantly less overhead than a prevailing tool for the profiling of Java code. Copyright © 2008 John Wiley & Sons, Ltd.     

PAST: accurate instrumentation on fully optimized program

Instrumentation is a powerful technique for monitoring, profiling, debugging, logging and tracing the software. In order to determine the instrumentation location, the user needs to know where the current executed location is in the source code. Previous instrumentation approaches rely on debugging information to find the location in the source code. For fully optimized programs, debugging information is not complete, which limits the application of those approaches. In this paper, we present pattern‐based abstract syntax tree (PAST) instrumentation, an ideal instrumentation methodology that accurately instruments the fully optimized program. The instrumentation location is specified in an intuitive way that matches the source code at the abstract syntax tree level. The program can be instrumented either at the compile time using the ordinary compiling or when it is running using the just‐in‐time compiling. Experimental results show that PAST can accurately instrument the target program. There is negligible run time overhead when the running program is instrumented without any operation. We have implemented PAST on both x86‐32 and x86‐64 to show that PAST is easily portable across different architecture. Copyright © 2015 John Wiley & Sons, Ltd.     

Development and performance analysis of real‐world applications for distributed and parallel architectures

Several large real‐world applications have been developed for distributed and parallel architectures. We examine two different program development approaches. First, the usage of a high‐level programming paradigm which reduces the time to create a parallel program dramatically but sometimes at the cost of a reduced performance; a source‐to‐source compiler, has been employed to automatically compile programs—written in a high‐level programming paradigm—into message passing codes. Second, a manual program development by using a low‐level programming paradigm—such as message passing—enables the programmer to fully exploit a given architecture at the cost of a time‐consuming and error‐prone effort. Performance tools play a central role in supporting the performance‐oriented development of applications for distributed and parallel architectures. SCALA—a portable instrumentation, measurement, and post‐execution performance analysis system for distributed and parallel programs—has been used to analyze and to guide the application development, by selectively instrumenting and measuring the code versions, by comparing performance information of several program executions, by computing a variety of important performance metrics, by detecting performance bottlenecks, and by relating performance information back to the input program. We show several experiments of SCALA when applied to real‐world applications. These experiments are conducted for a NEC Cenju‐4 distributed‐memory machine and a cluster of heterogeneous workstations and networks. Copyright © 2001 John Wiley & Sons, Ltd.     

基于符号执行的底层虚拟机混淆器反混淆框架

针对Miasm反混淆框架反混淆后的结果是一张图片,无法反编译恢复程序源码的问题,在对底层虚拟机混淆器（OLLVM）混淆策略和Miasm反混淆思路进行深入学习研究后,提出并实现了一种基于符号执行的OLLVM通用型自动化反混淆框架。首先,利用基本块识别算法找到混淆程序中有用的基本块和无用块;其次,采用符号执行技术确定各个有用块之间的拓扑关系;然后,直接对基本块汇编代码进行指令修复;最后,得到一个反混淆后的可执行文件。实验结果表明,该框架在保证尽量少的反混淆用时前提下,反混淆后的程序与未混淆源程序的代码相似度为96.7%,能非常好地实现x86架构下C/C++文件的OLLVM反混淆。     

Portable and accurate sampling profiling for Java

This article presents a novel framework for the sampling‐based profiling of Java programs, which relies on program transformation techniques. We exploit bytecode instruction counting to regularly activate a user‐defined profiling agent, which processes the current call stack. This approach has several advantages, such as making the instrumentation entirely portable, generating reproducible profiles, and enabling a fine‐grained adjustment of the sampling rate. Our framework offers a flexible API to write portable profiling agents in pure Java. While the overhead due to our profiling scheme is comparable to the overhead caused by prevailing, timing‐based profilers, the resulting profiles are much more accurate. Copyright © 2006 John Wiley & Sons, Ltd.     

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.     

Reducing the Overhead of Dynamic Analysis

Dynamic analysis (instrumenting programs with code to detect and preven errors during program execution) can be an effective approach to debugging, as well as an effective means to prevent harm 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.     

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.     

基于符号执行和N-scope复杂度的代码混淆度量方法

代码混淆可有效对抗逆向工程等各类 MATE 攻击威胁,作为攻击缓和性质的内生安全技术发展较为成熟,对代码混淆效果的合理度量具有重要价值。代码混淆度量研究相对较少,针对代码混淆弹性的度量方法与泛化性、实用性度量方法相对缺乏。符号执行技术广泛应用于反混淆攻击,其生成遍历程序完整路径输入测试集的难度可为混淆弹性度量提供参考,然而基于程序嵌套结构的对抗技术可显著降低符号执行效率,增加其混淆弹性参考误差。针对上述问题,提出结合符号执行技术和N-scope复杂度的代码混淆度量方法,该方法首先基于程序符号执行时间定义程序混淆弹性;其次提出适配符号执行的N-scope复杂度,定义程序混淆强度同时增强符号执行对多层嵌套结构程序的混淆弹性度量鲁棒性;进而提出结合动态分析与静态分析的混淆效果关联性分析,通过对程序进行符号执行与控制流图提取量化混淆效果。面向 C 程序构建了该度量方法的一种实现框架并验证,实验对3个公开程序集及其混淆后程序集约4 000个程序进行混淆效果度量,度量结果表明,提出的度量方法在较好地刻画混淆效果的同时拥有一定的泛化能力与实用价值;模拟真实混淆应用场景给出了该度量方法的使用样例,为混淆技术使用人员提供有效的混淆技术度量与技术配置参考。     

基于事务性执行的投机并行多线程软件模拟

基于事务性执行的投机并行多线程是一种适合未来多核微处理器架构的新型并行程序设计和编译技术.但在此基础上的并行程序执行过程更为复杂,程序执行过程的模拟成为关键问题之一.本文提出利用二进制代码级动态插桩技术对投机并行多线程程序进行功能性模拟,设计并实现了完整的软件平台,可精确地模拟和监控并行程序的线程级投机执行过程,检测访存冲突,从而实现投机并行多线程的语义.该软件平台同时可以作为进一步研究投机多线程并行程序真实执行过程的基础,并有效支持投机并行多线程编译器的设计和分析.     

基于动态二进制插桩的密钥安全性检测

针对加密软件中的密钥安全性问题,提出一种基于动态二进制插桩的密钥安全性检测方法。该方法面向CryptoAPI加密应用程序,首先通过对CryptoAPI密钥应用模式的分析,指出潜在的密钥安全性漏洞;然后以动态二进制分析平台Pin为支撑,动态记录程序运行期间的加解密过程信息;在此基础上设计关联性漏洞检测算法,实现对密钥安全性的检测。测试结果表明,该方法能够有效检测出两大类密钥安全性漏洞。     

Instruction-Based Online Periodic Self-Testing of Microprocessors with Floating-Point Units

Online periodic testing of microprocessors is a valuable means to increase the reliability of a low-cost system, when neither hardware nor time redundant protection schemes can be applied. This is particularly valid for floating-point (FP) units, which are becoming more common in embedded systems and are usually protected from operational faults through costly hardware redundant approaches. In this paper, we present scalable instruction-based self-test program development for both single and double precision FP units considering different instruction sets (MIPS, PowerPC, and Alpha), different microprocessor architectures (32/64-bit architectures) and different memory configurations. Moreover, we introduce bit-level manipulation instruction sequences that are essential for the development of FP unit's self-test programs. We developed self-test programs for single and double precision FP units on 32-bit and 64-bit microprocessor architectures and evaluated them with respect to the requirements of low-cost online periodic self-testing: fault coverage, memory footprint, execution time, and power consumption, assuming different memory hierarchy configurations. Our comprehensive experimental evaluations reveal that the instruction set architecture plays a significant role in the development of self-test programs. Additionally, we suggest the most suitable self-test program development approach when memory footprint or low power consumption is of paramount importance.     

Symbolic analysis via semantic reinterpretation

The paper presents a novel technique to create implementations of the basic primitives used in symbolic program analysis: forward symbolic evaluation, weakest liberal precondition, and symbolic composition. We used the technique to create a system in which, for the cost of writing just one specification—an interpreter for the programming language of interest—one obtains automatically generated, mutually-consistent implementations of all three symbolic-analysis primitives. This can be carried out even for languages with pointers and address arithmetic. Our implementation has been used to generate symbolic-analysis primitives for the x86 and PowerPC instruction sets.     

Symbolic execution with abstraction

We address the problem of error detection for programs that take recursive data structures and arrays as input. Previously we proposed a combination of symbolic execution and model checking for the analysis of such programs: we put a bound on the size of the program inputs and/or the search depth of the model checker to limit the search state space. Here we look beyond bounded model checking and consider state matching techniques to limit the state space. We describe a method for examining whether a symbolic state that arises during symbolic execution is subsumed by another symbolic state. Since the number of symbolic states may be infinite, subsumption is not enough to ensure termination. Therefore, we also consider abstraction techniques for computing and storing abstract states during symbolic execution. Subsumption checking determines whether an abstract state is being revisited, in which case the model checker backtracks—this enables analysis of an under-approximation of the program behaviors. We illustrate the technique with abstractions for lists and arrays. We also discuss abstractions for more general data structures. The abstractions encode both the shape of the program heap and the constraints on numeric data. We have implemented the techniques in the Java PathFinder tool and we show their effectiveness on Java programs. This paper is an extended version of Anand et al. (Proceedings of SPIN, pp. 163–181, 2006).     

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

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

An Integrated Path and Timing Analysis Method based on Cycle-Level Symbolic Execution

Previously published methods for estimation of the worst-case execution time on high-performance processors with complex pipelines and multi-level memory hierarchies result in overestimations owing to insufficient path and/or timing analysis. This does not only give rise to poor utilization of processing resources but also reduces the schedulability in real-time systems. This paper presents a method that integrates path and timing analysis to accurately predict the worst-case execution time for real-time programs on high-performance processors. The unique feature of the method is that it extends cycle-level architectural simulation techniques to enable symbolic execution with unknown input data values; it uses alternative instruction semantics to handle unknown operands. We show that the method can exclude many infeasible (or non-executable) program paths and can calculate path information, such as bounds on number of loop iterations, without the need for manual annotations of programs. Moreover, the method is shown to accurately analyze timing properties of complex features in high-performance processors using multiple-issue pipelines and instruction and data caches. The combined path and timing analysis capability is shown to derive exact estimates of the worst-case execution time for six out of seven programs in our benchmark suite.     

Optimization of VLIW compatibility systems employing dynamic rescheduling

Lack of object code compatibility in VLIW architectures is a severe limit to their adoption as a general-purpose computing paradigm. Previous approaches include hardware and software techniques, both of which have drawbacks. Hardware techniques add to the complexity of the architecture, whereas software techniques require multiple executables. This paper presents a technique called Dynamic Rescheduling that applies software techniques dynamically, using intervention by the OS: at each first-time page fault, the page of code is rescheduled for the new generation, if required. Results are presented to demonstrate the viability of the technique using the Illinois IMPACT compiler and the TINKER architectural framework. For the machine models and the workloads used in this study, performance of the rescheduled code compares well with the native scheduled code for a machine. The behavior of a subset of programs in the workload is such that they face a large number of first-time page faults. Due to this, their rescheduling overhead is higher relative to their total execution time. Such programs are calledhigh-overhead programs. Caching of translated pages across multiple invocations of the program to reduce the rescheduling overhead, using apersistent rescheduled-page cache (PRC) ⁽¹⁾ is discussed. It was found that for the workload used in this evaluation, a PRC of size between 512 to 1024 pages, and which uses anoverhead-based page replacement policy would be effective in reducing the overhead. This is a revised and expanded version of the paper presented by the authors at the28th Annual International Symposium on Microarchitecture (MICRO-28), November 1995, Ann Arbor, Michigan.     

基于插桩和布尔逻辑的运行时程序验证框架

针对软件测试和静态程序验证中存在的连续性程序执行验证和推理问题,提出一个基于程序插桩和布尔逻辑的运行时程序验证框架——RPA。定义一种用于描述运行时程序性质和规范的动态逻辑语言RPAL,实现自动化插桩以收集运行时程序状态信息,设计一个支持高效验证的句子调度算法。实验结果表明,结合合适的谓词扩展,RPA可以有效地验证和分析软件逻辑,发现潜在的软件错误。     

一种基于DBI的ROP攻击检测

随着Return-Oriented Programming(ROP)思想的提出,程序安全面临新的挑战。ROP攻击操作粒度细致,特征隐蔽,构造精巧,静态特征稀少,因此传统的安全防御措施很难对之有效。在这种背景下,利用执行时的动态特征去识别、防御ROP攻击变得非常重要。Dynamic Binary Instrumentation(DBI)技术的引入,为ROP攻击动态特性分析提供了有力的支持。介绍一种利用DBI分析技术识别ROP攻击序列的方法,即通过识别恶意的程序执行流,约束库函数的调用规范,来检测ROP攻击。与此同时,还设计了一套可扩展的程序防御框架,用于检测程序的扩展,由此说明该检测工具的通用性与可扩展性。