基于IDA-Pro的软件逆向分析方法

二进制程序转换作为软件逆向分析的主要手段发挥着积极作用。该文给出一种程序转换方法,应用软件二进制程序经IDA Pro反汇编得汇编语言程序,依据下推自动机原理设计汇编文法识别该汇编文件、制定相应的转换规则和优化措施将汇编语言转换成中间语言。转换所得中间语言可读性较强,具有通用性且易于理解。该方法达到了较高的自动化程度,缩小了目标程序的代码量,其应用可有效地减少软件分析和调试人员在追踪代码时所需的时间和工作量。给出应用上述方法进行程序转换的实例。     

基于GCC关键变量数据流分析算法的程序切片技术

随着程序的规模的扩大和复杂度的提高,通过直接分析源码进行程序切片,变得十分困难。在现有的利用编译优化技术来优化程序切片的方法中,存在无法有效利用程序的编译时信息和编译器的优化技术,以及对语言的支持不完善的问题。为此,分析了GCC编译器在编译时的中间表示,首次提出了基于GCC关键变量数据流分析算法的程序切片技术,以程序的GIMPLE中间表示为基础,以程序基本块为单位,通过迭代求解数据流方程,分析程序基本块内和不同基本块间的关键变量数据流信息。该程序切片技术可以获取源程序中仅与预设目标函数相关的关键变量和关键语句,缩减程序规模。最后通过实验,证明了该算法的可行性。     

Modeling and optimizing large-scale data flows

Modern scientific collaborations require large-scale integration of various processes. Higher-level dataflow languages are used on top of parallel and distributed dataflow systems to enable faster data-intensive workflow programs development, their easier optimization, and more maintainable code. In this paper, we present the rationales, design, and application of the needed advanced support for modeling and optimizing data flows for data mining and integration processes. The optimization research and development is based on dataflow pre-execution modeling and extending the registry of process activities by advanced annotations. Additionally, the overall process from a dynamic model to a static model as input for the optimization algorithms is described. This novel approach is implemented within an advanced graphical user interface, called the Process Designer, in order to support semi-automatic optimization as well as within a dataflow execution platform, called the Gateway. It can be adapted to any dataflow language implementation. The Process Designer architecture based on modern (meta-)modeling concepts naturally supports validated transformations between external textual and internal graphical representations of the targeted dataflow language, and in this way significantly increases the productivity and robustness of the implementation processes.     

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.     

Structured dataflow analysis for arrays and its use in an optimizing compiler

We extend the well-known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations. This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part. The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile-time cost of obtaining and using it.     

应用数据流分析法求解程序运行时信息相关问题的研究

介绍了编译优化过程中非常重要的一种分析--数据流分析.数据流分析揭示了程序数据之间的相互关系,并为后续的编译优化提供信息.通过举例说明了求解数据流问题的基本步骤,阐述了其基本概念和理论框图,并引出了求解数据流分析问题的基本算法和两个重要结论.最后介绍若干使用本求解框架求解的经典的数据流问题.     

A method of program transformation between variable sharing and message passing

There have been proposed and used many programming concepts for realizing interprocess communication and synchronization, and two fundamental categories among them are variable sharing (e.g. semaphores) and message passing (signals, input/output in CSP and redezvous in Ada). The aim of this paper is to investigate the relationship between these two mechanisms, and in particular, program transformation between them. We here propose a transformation method between parallel programs written in each of these two, which uses transformation schemes named monitor transformations. We exhibit the method by showing through a chain of program transformations the equivalence of two versions of a parallel algorithm called dynamic sorting array.     

Exploiting fine-grain parallelism on dataflow architectures

Although dataflow computers have many attractive features, skepticism exists concerning their efficiency in handling arrays (vectors) in high performance scientific computation. This paper outlines an efficient implementation scheme for arrays in applicative languages (such as VAL and SISAL) based on the principles of dataflow software pipelining. It illustrates how the fine-grain parallelism of dataflow approach can effectively handle large amount of data structured in applicative array operations. This is done through dataflow software pipelining between pairs of code blocks which act as producer-consumer of array values. To make effective use of the pipelined code mapping scheme, a compiler needs information concerning the overall program structure as well as the structure of each code block. An applicative language provides a basis for such analysis.

The program transformation techniques described here are developed primarily for the computationally intensive part of a scientific numerical program, which is usually formed by one or a few clusters of acyclic connected code blocks. Each code block defines an array value from several input arrays. We outline how mapping decisions of arrays can be based on a global analysis of attributes of the code blocks. We emphasize the role of overall program structure and the strategy of global optimization of the machine code structure. The structure of a proposed dataflow compiler based on the scheme described in this paper is outlined.     

Extensible intraprocedural flow analysis at the abstract syntax tree level

We have developed a new approach for implementing precise intraprocedural control-flow and dataflow analyses at the abstract syntax tree level. Our approach is declarative, making use of reference attribute grammars augmented with circular attributes and collection attributes. This results in concise executable specifications of the analyses, allowing extensions both to the language and with further source code analyses.     

Circular attribute grammars with remote attribute references and their evaluators

Attribute grammars (AGs) are a suitable formalism for the development of language processing systems. However, for languages including unrestricted labeled jumps, such as “goto” in C, the optimizers in compilers are difficult to write in AGs. This is due to two problems that few previous researchers could deal with simultaneously, i.e., references of attribute values on distant nodes and circularity in attribute dependency. This paper proposescircular remote attribute grammars (CRAGs), an extension of AGs that allows (1) direct relations between two distant attribute instances through pointers referring to other nodes in the derivation tree, and (2) circular dependencies, under certain conditions including those that arise from remote references. This extension gives AG programmers a natural means of describing language processors and programming environments for languages that include any type of jump structure. We also show a method of constructing an efficient evaluator for CRAGs called amostly static evaluator. The performance of the proposed evaluator has been measured and compared with dynamic and static evaluators. Akira Sasaki: He is a research fellow of the Advanced Clinical Research Center in the Institute of Medical Science at the University of Tokyo. He received his BSc and MSc from Tokyo Institute of Technology, Japan, in 1994 and 1996, respectively. His research interests include programming languages, programming language processors and programming environments, especially compiler compilers, attribute grammars and systematic debugging. He is a member of the Japan Society for Software Science and Technology. Masataka Sassa, D.Sc.: He is Professor of Computer Science at Tokyo Institute of Technology. He received his BSc, MSc and DSc from the University of Tokyo, Japan, in 1970, 1972 and 1978, respectively. His research interests include programming languages, programming language processors and programming environments, currently he is focusing on compiler optimization, compiler infrastructure, attribute grammars and systematic debugging. He is a member of the ACM, IEEE Computer Society, Japan Society for Software Science and Technology, and Information Processing Society of Japan.     

Semantic equivalence of covering attribute grammars

This paper investigates some methods for proving the equivalence of different language specifications that are given in terms of attribute grammars. Different specifications of the same language may be used for different purposes, such as language definition, program verification, or language implementation. The concept of syntactic coverings is extended to the semantic part of attribute grammars. Given two attribute grammars, the paper discusses several propositions that give sufficient conditions for one attribute grammar to be semantically covered by the other one. These tools are used for a comparison of two attribute grammars that specify syntax and semantics of mixed-type expressions. This example shows a trade-off between the complexity of syntactic and semantic specifications. Another example discussed is the equivalence of different attribute grammars for the translation of the while-statement, as used in compilers for top-down and bottom-up syntax analysis.This work was in part supported by the National Research Council of Canada.     

Tail recursion transformation in functional dataflow parallel programs

The peculiarities of transforming functional dataflow parallel programs into programs with finite resources are analysed. It is considered how these transformations are affected by the usage of asynchronous lists, the return of delayed lists and the variation of the data arrival pace relative to the time of its processing. These transformations allow us to generate multiple programs with static parallelism based on one and the same functional dataflow parallel program.     

Characterization of program loops in code optimization

Recent work in code optimization has led to development of new unified optimizing transformations[6,7]. Application of these transformations requires solution of bi-directional data flow problems over program flow graphs using iterative solution techniques. Appropriate characterization of program loops in the flow graph is necessary so as (i) not to hinder code movement, etc., and (ii) restrict optimization overheads to low levels. This paper reviews alternate loop characterizations and proposes a characterization which leads to minimum overheads and has certain nice properties from a practical viewpoint.     

Iteration of transformation passes over attributed program trees

Summary Transformations of attributed program trees form an essential part of compiler optimizations. A strategy of repeatedly applying alternate attribute evaluation and tree transformation phases is discussed. An attribute evaluation phase consists of a sequence of passes over the tree. A tree transformation phase consists of a single pass, which is never interrupted to carry out a re-evaluation. Both phases can be performed in parallel. This strategy requires a distinction between consistent (i.e., correct) and approximate attribute values. Tree transformations can be considered safe if they guarantee that the attribute values everywhere in the program tree will remain consistent or will become at least approximations of the consistent values, so that subsequent transformations can be applied correctly.This attribute evaluation and tree transformation strategy shows similarities with the evaluation methods for circular attribute grammars.     

Analysis and generation grammars

This paper describes the analysis and generation grammars for English and Japanese as they were employed in the KBMT-89 program. We discuss word order, coordination, subcategorization, morphological rules, rule ordering and bi-directional grammars.     

Carrying on the legacy of imperative languages in the future parallel computing era

There has been a renewed interest in dataflow computing models in recent years of technology scaling. Potentiality of exploiting huge parallelism, with the expense of low power, simpler circuit, less silicon area, is the main characteristic of a dataflow model. Growing trends in housing large number of functional units in a single chip, making use of local clocks, reducing energy consumptions, avoiding global wires are the main reasons behind the resurgence of dataflow models. To program a dataflow machine, new architectures suggest imperative languages rather than functional type dataflow languages or parallel languages because this is the right way to make the new architectures popular among the general community. Although for several decades scientists have been working on how imperative languages can be used in dataflow models efficiently, there is no systematic review on those works. Existing reviews on dataflow paradigm mainly focus on the architectures. Although few papers review programming languages of dataflow architectures, their discussions are limited to only dataflow languages and visual programming languages which are fundamentally different from imperative languages. In this paper, we conduct a systematic review on those works that attempt to provide a way to use imperative languages in any type of dataflow architectures. Our survey of compilers and related architectures cover the aspects like translation mechanisms of program construct, their optimization techniques, memory ordering methods, program allocation and scheduling and special architectural features. We also present some of our observations and future research directions obtained by exploring the literature.     

Using Verified Data-Flow Analysis-based Optimizations in Attribute Grammars

Building verified compilers is difficult, especially when complex analyses such as type checking or data-flow analysis must be performed. Both the type checking and program optimization communities have developed methods for proving the correctness of these processes and developed tools for using, respectively, verified type systems and verified optimizations. However, it is difficult to use both of these analyses in a single declarative framework since these processes work on different program representations: type checking on abstract syntax trees and data-flow analysis-based optimization on control flow or program dependency graphs.We present an attribute grammar specification language that has been extended with constructs for specifying attribute-labelled control flow graphs and both CTL and LTL-FV formulas that specify data-flow analyses. These formulas are model-checked on these graphs to perform the specified analyses. Thus, verified type rules and verified data-flow analyses (verified either by hand or with automated proof tools) can both be transcribed into a single declarative framework based on attribute grammars to build a high-confidence language implementations. Also, the attribute grammar specification language is extensible so that it is relatively straight-forward to add new constructs for different temporal logics so that alternative logics and model checkers can be used to specify data-flow analyses in this framework.     

Three Improvements on an Incremental Algorithm for Automatic Semantic Analysis

The formalism of attribute grammars is a powerful tool for specifying the static semantics of programming languages,and attribute evaluation provides an effective approach to automatic semantic analysis.The author previously proposed a time-optimal algorithm for incremental evaluation of ordered attribute grammars.In this paper,three improvements are suggested upon the algorithm so that it not only allows multiple subtree replacements,but also cancels three auxiliary tables required before,For experimental purposes,the improved algorithm has been implemented in Pascal on Motorola 68010     

Inductive attribute grammars

Attribute grammars are traditionally constrained to be noncircular. In using attribute grammars to specify the semantics of programming languages, this noncircularity limitation has restricted attribute grammars to compile-time or static semantics. Inductive attribute grammars add a general form of circularity to this standard approach. Inductive attribute grammars have the expressiveness required to describe the full semantics of programming languages, while at the same time maintaining the declarative character of standard attribute grammars. This expanded view of attribute grammars proves to be useful in interactive language-based programming environments, as inductive attribute grammars allow the environment to provide an interpreter for incremental re-evaluation of programs after small changes to the code. The addition of run-time semantics via circular attribute grammars permits automatically generated environments to be complete, in that incremental static semantic checking and fast incremental execution are now available within a single framework.The authors' present affiliations are the United States Geological Survey and the Northrop Corporation respectively.