A System for Generating Reverse Engineering Tools: A Case Study of Software Modularisation

The paper presents a case study in the development of software modularisation tools. The tools are produced by using a system for developing code analysers that uses a database to store both a no-loss fine-grained intermediate representation and the analyses' results. The analysers are automatically generated from a high-level specification of the desired analyses expressed in a domain-oriented language. We use a program intermediate representation, called F(p), as the user-visible data base conceptual model. Analysers are specified in a declarative language, called F(p) – , which allows the specification of an analysis in the form of a traversal of an algebraic expression, with accesses to, and stores of, the database information the algebraic expression indexes. A foreign language interface allows the analysers to be embedded into C programs. This is useful, for example, to implement the user interface of an analyser or to facilitate interoperation of the generated analysers with pre-existing tools.     

Automatic source-code parallelization using HICOR objects

We show that by using an intermediate representation, which supports a formalized interface on which to construct parallelization tools, the mapping of the representation onto parallel architectures can be performed quickly and efficiently. An intermediate representation called HICOR (Hierarchical Intermediate Code Object Representation) is shown to facilitate the exploitation of parallel operations by providing an abstraction layer for performing high-level intermediate code analysis, scheduling, and code generation. An object-oriented design approach has been employed in the development of HICOR and associated tools. Source language constructs are transformed into specialized object classes. Inheritance properties provided by the object-oriented paradigm are utilized to provide a common interface to each object in the HICOR representation. It is this interface that provides the needed consistency and flexibility in which to construct tools that has since been lacking. In particular, a tool to performCompile-Time Scheduling is presented. The scheduling algorithm employed differs from traditional scheduling problems in that merging of tasks is performed to reduce both task creation and communication costs in determining the final schedule. Architectural parameters are provided as input to the heuristic allowing the scheduler to produce near-optimal results for a wide variety of MIMD architectures. Once the final schedule is determined theTarget Code Generator, also presented, is used to generate the corresponding target code. A prototype system has been implemented in C++ which incorporates the HICOR intermediate representation with the tools described. The target architectures include the Sun 630 MP/4, Sequent Symmetry S81, and Stardent Titan.     

SCRUB: a tool for code reviews

This paper describes a tool called Source Code Review User Browser (SCRUB) that was developed to support a more effective and tool-based code review process. The tool was designed to support a large team-based software development effort of mission critical software at JPL, but can also be used for individual software development on small projects. The tool combines classic peer code review with machine-generated analyses from a customizable range of source code analyzers. All reports, whether generated by humans or by background tools, are accessed through a single uniform interface provided by SCRUB.     

Structure and software tools of AIDA

AIDA consists of a set of software tools to allow for fast development and easy-to-maintain Medical Information Systems. AIDA supports all aspects of such a system both during development and operation. It contains tools to build and maintain forms for interactive data entry and on-line input validation, a database management system including a data dictionary and a set of run-time routines for database access, and routines for querying the database and output formatting. Unlike an application generator, the user of AIDA may select parts of the tools to fulfill his needs and program other subsystems not developed with AIDA. The AIDA software uses as host language the ANSI-standard programming language MUMPS, an interpreted language embedded in an integrated database and programming environment. This greatly facilitates the portability of AIDA applications. The database facilities supported by AIDA are based on a relational data model. This data model is built on top of the MUMPS database, the so-called global structure. This relational model overcomes the restrictions of the global structure regarding string length. The global structure is especially powerful for sorting purposes. Using MUMPS as a host language allows the user an easy interface between user-defined data validation checks or other user-defined code and the AIDA tools. AIDA has been designed primarily for prototyping and for the construction of Medical Information Systems in a research environment which requires a flexible approach. The prototyping facility of AIDA operates terminal independent and is even to a great extent multi-lingual. Most of these features are table-driven; this allows on-line changes in the use of terminal type and language, but also causes overhead. AIDA has a set of optimizing tools by which it is possible to build a faster, but (of course) less flexible code from these table definitions. By separating the AIDA software in a source and a run-time version, one is able to write implementation-specific code which can be selected and loaded by a special source loader, being part of the AIDA software. This feature is also accessible for maintaining software on different sites and on different installations.     

Reverse engineering: Algorithms for program graph production

The paper proposes an algebraic representation of program modules, called F(p), and illustrates the algorithms that use F(p) to generate program graph models for measurement, documentation and testing activities. The representation refers to procedural languages, D-structured programs and one-in/one-out modules but its definition can be extended to programs structured in terms of an arbitrary set of one-in/one-out legal control structures. Since it is possible to produce F(p) directly from the program code using reverse engineering techniques, the algorithms proposed are of considerable interest for the setting up of tools supporting the program comprehension phase, which is a fundamental first step in any maintenance operation.     

The Design for a Secure System Based on Program Analysis

This paper describes the design of a prototype experimental secure operating system kernel called xsl that supports compile-time enforcement of an information flow policy. The security model chosen is an extension of Feiertag's model modified to state requirements in terms of program analysis functions. A prototype flow analyzer for Pascal programs, based on Denning's model, has been designed and implemented for incorporation into xs1. In addition, a flow analyzer, based on London's model, has also been designed and implemented. Both kinds of enforcement are supported in xsl. Both program anallyzers use an intermediate code program representation, originally designed for code optimization. Implementation of the flow analyzers is in Euclid with the remainder of xsl in PascaL     

VHDL中间数据格式及其设计库

VHDL中间数据格式(VIDF)是VHDL设计环境(VDE)的要求,用来作为VDE中各设计工具的一个公共数据界面.VIDF允许它的开发者根据要求采用不同的实现方法.本文给出的是一种借鉴Ada的中间语言Diana而产生的VIDF表示,这种表示使得VIDF的形式较规范化.VIDF是存放在VHDL设计库(VDL)中的,本文也介绍了VDL的一种实现方法.     

Cobra: a light-weight tool for static and dynamic program analysis

Static source code analysis tools have become indispensable for the development of reliable software applications. The best analyzers can reveal subtle flaws in a code base, but they can also be slow. In part this is due to the collection of detailed information about the possible data and control flow of an application to support the broadest possible range of analyses. For larger code bases it is not unusual that even the best of breed static analyzers can take an hour or more to complete an analysis. In this paper we describe a framework for a much faster, but more light-weight type of static analysis that can support interactive use for standard types of queries. The Cobra tool we designed for this purpose can scale to explore millions of lines of code interactively. The tool is mostly language agnostic, and can therefore easily be configured to resolve even dynamic program analysis queries.     

Decompilation of Java bytecode to Prolog by partial evaluation

Reasoning about Java bytecode (JBC) is complicated due to its unstructured control-flow, the use of three-address code combined with the use of an operand stack, etc. Therefore, many static analyzers and model checkers for JBC first convert the code into a higher-level representation. In contrast to traditional decompilation, such representation is often not Java source, but rather some intermediate language which is a good input for the subsequent phases of the tool. Interpretive decompilation consists in partially evaluating an interpreter for the compiled language (in this case JBC) written in a high-level language with respect to the code to be decompiled. There have been proofs-of-concept that interpretive decompilation is feasible, but there remain important open issues when it comes to decompile a real language such as JBC. This paper presents, to the best of our knowledge, the first modular scheme to enable interpretive decompilation of a realistic programming language to a high-level representation, namely of JBC to Prolog. We introduce two notions of optimality which together require that decompilation does not generate code more than once for each program point. We demonstrate the impact of our modular approach and optimality issues on a series of realistic benchmarks. Decompilation times and decompiled program sizes are linear with the size of the input bytecode program. This demonstrates empirically the scalability of modular decompilation of JBC by partial evaluation.     

A form-based natural language front-end to a CIM database

The paper presents a methodology for developing a user interface that combines fourth generation interface tools (SQL forms) with a natural language processor for a database management system. The natural language processor consists of an index, a lexicon and a parser. The index is used to uniquely identify each form in the system through a conceptual representation of its purpose. The form fields specify database or nondatabase fields whose values are either entered by the user (user-defined) or are derived by the form (system-defined) in response to user input. A set of grammar rules are associated with each form. The lexicon consists of all words recognized by the system, their grammatical categories, roots, their associations (if any) with database objects and forms. The parser scans, a natural language query to identify a form in a bottom-up fashion. The information requested in the user query is determined in a top-down manner by parsing, through the grammar rules associated with the identified form. Extragrammatical inputs with limited deviations from the grammar rules are supported. Combining a natural language processor with SQL forms allows processing data modification tasks without violating any database integrity constraint, having duplicate records, or entering invalid data. A prototype natural language interface is described as a front-end to an ORACLE database for a computer integrated manufacturing system     

基于流分析的可执行程序结构化表示工具

直接面向可执行程序进行安全漏洞分析时,首先需要得到二进制代码的中间语言表示。探讨了流分析技术在汇编代码理解中的应用,并在Linux平台上实现了一个轻量级汇编代码结构化表示工具BESTAR。该系统利用控制流和数据流分析技术识别通用控制结构,分析程序执行流,重构表达式和函数,发现数据依赖关系,将汇编代码转换成一个结构化、易理解的中间语言程序,为进一步进行安全分析打下了基础。     

Towards a simple and safe Objective Caml compiling framework for the synchronous language SIGNAL

This paper presents a simple and safe compiler, called MinSIGNAL, from a subset of the synchronous dataflow language SIGNAL to C, as well as its existing enhancements. The compiler follows a modular architecture, and can be seen as a sequence of source-to-source transformations applied to an intermediate representation which is named Synchronous Clocked Guarded Actions (S-CGA) and translation to sequential imperative code. Objective Caml (OCaml) is used for the implementation of MinSIGNAL. As a modern functional language, OCaml is adapted to symbolic computation and so, particularly suitable for compiler design and implementation of formal analysis tools. In particular, the safety of its type checking allows to skip some verification that would be mandatory with other languages. Additionally, this work is a basis for the formal verification of the compilation of SIGNAL with a theorem prover such as Coq.     

用于漏洞检测的中间语言表示方法

现有Web漏洞检测方法中使用的中间语言针对特定编程语言设计,在对多种编程语言源代码进行漏洞抽象表示时,无法将多语言下的同类型漏洞用统一的中间语言表示,增加了后续漏洞分析处理的难度。针对该问题提出了一种基于污点分析的中间语言表示方法,实现多编程语言下同类型漏洞信息的统一抽象表示。该中间语言设计过程中将漏洞发生过程抽象为三元组表示,将与三元组相关的代码元素抽象为中间语言的关键字,根据三元组间的语义关系设计了该中间语言的语法。在转义时,利用污点分析方法跟踪污染源的执行路径,对路径中的源代码进行转义得到中间语言表示。最后将该中间语言用于漏洞检测模型,实验结果表明该中间语言与对照中间语言相比对编程语言中漏洞信息的抽象表示更具普适性,对漏洞检测具有有效性。     

Metaform: updatable form screens and their application to the use of office metaphors in query language instruction

Abstract

A database interface language and system, called Metaform, which automatically generates multi-relational form screen interfaces for use by non-computer professionals has been developed. A form screen is a subset of the relational database, with a particular relation or combination of relations being represented. Through form screens, users can simultaneously query and update several relations in the database without having to know about its underlying structure. An overview of the Metaform system is presented and several examples of the use of the Metaform query language and update operators are described.

A series of ‘usability’ studies were conducted on a prototype of the Metaform system to examine the claims that the form concept aids computer-naive users in building complex database queries. These studies adopted the form screen concept to present six office paper work analogies to users to help them to understand the database retrieval concepts. The analogies of a file cabinet, a file folder, a stack of forms, a single form, a table of information on a form and a field of information were used in a two-staged training module.

At the end of each training sequence, users answered questions with the prototype and with paper and pencil which tapped their understanding of the database retrievals they were learning to perform. The results from these questionnaires were mixed. Users performed successful relational queries for simple retrievals and for those using existential quantifiers. They had difficulty with queries involving multiple steps and intermediate stages. Although users understood and used the analogies, they ran into difficulties with the ambiguities in the English statements of the queries, thus suggesting a need for another level of metaphors and/or problem representation tools not associated with the machine but with the user's comprehension of database retrieval problems.     

A knowledge-based prototyping environment for construction of scientific modeling software

Over the past 30 years, scientific software models have played an increasingly prominent role in the conduct of science. Unfortunately, scientific models can be difficult and time-consuming to implement, and there is little software engineering support specifically available for constructing scientific models. Because these models are not easily specified to scientifically-naive programmers, and because the scientist requires intimate knowledge of the code to conduct experiments, many scientists implement their own models. This coding activity takes valuable time away from their primary scientific mission. We have developed a knowledge-based software development tool that assists scientists in prototyping scientific models. With a specialized graphical user interface, the scientist constructs a high-level visual specification that captures the essential computational dependencies in the desired model. The system uses its scientific domain knowledge to ensure that the model being built is consistent and coherent. The final product is an executable prototype of a scientific model. Our tool accelerates the model-building process and eliminates the scientist's need to program in a formal language. Furthermore, the models developed with this tool are easier to understand and reuse than typical low-level scientific modeling code. At present, models developed with our system are restricted to those involving non-coupled algebraic and first order ordinary differential equations. Research is ongoing to lessen this restriction and support models with simultaneous equations.     

Metaform: updatable form screens and their application to the use of office metaphors in query language instruction

A database interface language and system, called Metaform, which automatically generates multi-relational form screen interfaces for use by non-computer professionals has been developed. A form screen is a subset of the relational database, with a particular relation or combination of relations being represented. Through form screens, users can simultaneously query and update several relations in the database without having to know about its underlying structure. An overview of the Metaform system is presented and several examples of the use of the Metaform query language and update operators are described.

A series of 'usability' studies were conducted on a prototype of the Metaform system to examine the claims that the form concept aids computer-naive users in building complex database queries. These studies adopted the form screen concept to present six office paper work analogies to users to help them to understand the database retrieval concepts. The analogies of a file cabinet, a file folder, a stack of forms, a single form, a table of information on a form and a field of information were used in a two-staged training module.

At the end of each training sequence, users answered questions with the prototype and with paper and pencil which tapped their understanding of the database retrievals they were learning to perform. The results from these questionnaires were mixed. Users performed successful relational queries for simple retrievals and for those using existential quantifiers. They had difficulty with queries involving multiple steps and intermediate stages. Although users understood and used the analogies, they ran into difficulties with the ambiguities in the English statements of the queries, thus suggesting a need for another level of metaphors and/or problem representation tools not associated with the machine but with the user's comprehension of database retrieval problems.     

Automatic Generation of Language-based Tools

Many tools can be automatically derived from formal language definitions, such as compilers/interpreters, editors, analyzers, visualizers/animators, etc. Some examples of language-based tools generated automatically by the LISA system are described in the paper. In addition the specification of an algorithm animator and program visualizer, Alma, generated from an extended LISA input-grammar is discussed; LISA principles and code are reused in Alma implementation.     

Type-Safe Code Transformations in Haskell

The use of typed intermediate languages can significantly increase the reliability of a compiler. By type-checking the code produced at each transformation stage, one can identify bugs in the compiler that would otherwise be much harder to find. We propose to take the use of types in compilation a step further by verifying that the transformation itself is type correct, in the sense that it is impossible that it produces an ill typed term given a well typed term as input.We base our approach on higher-order abstract syntax (HOAS), a representation of programs where variables in the object language are represented by meta-variables. We use a representation that accounts for the object language's type system using generalized algebraic data types (GADTs). In this way, the full binding and type structure of the object language is exposed to the host language's type system. In this setting we encode a type preservation property of a CPS conversion in Haskell's type system, using witnesses of a type correctness proof encoded in a GADT.     

Compiling real-time programs with timing constraint refinement andstructural code motion

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time correctness, without overconstraining the system. Moreover, an optimizing compiler can exploit this looser semantics to help tune the code, so that its worst-case execution time is consistent with its real-time requirements. In this paper we describe such a transformation system, which works in two phases. First, the TCEL source code is translated into an intermediate representation. Then an instruction-scheduling algorithm rearranges selected unobservable operations and synthesizes tasks guaranteed to respect the original event-based constraints