Fast and precise points-to analysis

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, software engineering applications used in an edit-compile cycle need points-to analysis to be fast and precise.In this article, we present a new context- and flow-sensitive approach to points-to analysis where calling contexts are distinguished by the points-to sets analyzed for their call target expressions. Compared to other well-known context-sensitive techniques it is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments using a number of abstract precision metrics and a concrete client application: escape analysis.     

C语言的别名分析方法研究

别名分析对于数据流分析、程序优化和分析工具的实现非常重要.文章提出了一种需求驱动,流非敏感的分析算法来解决指针别名问题.通过构造程序表达式图(PEG)把指针别名问题转化成判断两个指针节点是否是联通的问题,它不同于传统的别名分析方法,它不需要构造别名集合和对其求交集,所以提高了分析指针别名的效率.     

A system to assist survey analysts

The researcher who knows little about computers but wants to conduct a survey and analyse the results by computer can land himself in some difficulty if he does not appreciate some of the problems of computerization. This paper describes a system which is designed to aid such a person by providing assistance with the design of the questionnaire, the capturing of the data and the final analyses.     

Cost analysis of object-oriented bytecode programs

Cost analysis statically approximates the cost of programs in terms of their input data size. This paper presents, to the best of our knowledge, the first approach to the automatic cost analysis of object-oriented bytecode programs. In languages such as Java and C#, analyzing bytecode has a much wider application area than analyzing source code since the latter is often not available. Cost analysis in this context has to consider, among others, dynamic dispatch, jumps, the operand stack, and the heap. Our method takes a bytecode program and a cost model specifying the resource of interest, and generates cost relations which approximate the execution cost of the program with respect to such resource. We report on COSTA, an implementation for Java bytecode which can obtain upper bounds on cost for a large class of programs and complexity classes. Our basic techniques can be directly applied to infer cost relations for other object-oriented imperative languages, not necessarily in bytecode form.     

A novel analysis space for pointer analysis and its application for bug finding

The size of today’s programs continues to grow, as does the number of bugs they contain. Testing alone is rarely able to flush out all bugs, and many lurk in difficult-to-test corner cases. An important alternative is static analysis, in which correctness properties of a program are checked without running it. While it cannot catch all errors, static analysis can catch many subtle problems that testing would miss.We propose a new space of abstractions for pointer analysis—an important component of static analysis for C and similar languages. We identify two main components of any abstraction—how to model statement order and how to model conditionals, then present a new model of programs that enables us to explore different abstractions in this space. Our assign-fetch graph represents reads and writes to memory instead of traditional points-to relations and leads to concise function summaries that can be used in any context. Its flexibility supports many new analysis techniques with different trade-offs between precision and speed.We present the details of our abstraction space, explain where existing algorithms fit, describe a variety of new analysis algorithms based on our assign-fetch graphs, and finally present experimental results that show our flow-aware abstraction for statement ordering both runs faster and produces more precise results than traditional flow-insensitive analysis.     

The use of protocol analysis for determining ability requirements for personnel selection on a computer-based task

Abstract

The role of cognitively oriented tasks in the workplace continues to increase as automation of physical task components advances. Difficulties in automating the operator's cognitive processes have placed a renewed emphasis on the human component in advanced manufacturing systems. While traditional task analysis techniques have made significant contributions to improving productivity when important task elements are visually observable, their focus on manual task procedures make them less effective for cognitively oriented activities. This research has made a first attempt at integrating techniques from several disciplines to develop a cognitive task analysis methodology. The utility of this combined approach is examined for a new system being tested in the United States Postal Service. This task requires operators to encode, via a keyboard, addresses presented on a video display terminal. Results support the hypothesis that, for cognitively oriented tasks, a consensus based analysis technique (the Position Analysis Questionnaire) can be significantly improved by including data from task analysis provided the methodology is suitable for identifying non-physical task components.     

代谢组学数据处理研究的进展

代谢组学是继基因组学和蛋白质组学之后,于上世纪90年代新近发展起来的一个新的科学研究热点.代谢组学数据往往非常复杂,因此数据处理已经成为代谢组学研究中的关键技术和瓶颈之一.本文按照代谢组学数据预处理一代谢物靶标分析和代谢轮廓分析中的数据处理-代谢指纹分析中的数据处理的线索,评述国内外在代谢组学数据处理方面的最新进展,并介绍代谢组学数据处理软件.     

Making context‐sensitive inclusion‐based pointer analysis practical for compilers using parameterised summarisation

Because of its high precision as a flow‐insensitive pointer analysis, Andersen's analysis has been deployed in some modern optimising compilers. To obtain improved precision, we describe how to add context sensitivity on top of Andersen's analysis. The resulting analysis, called ICON , is efficient to analyse large programs while being sufficiently precise to drive compiler optimisations. Its novelty lies in summarising the side effects of a procedure by using one transfer function on virtual variables that represent fully parameterised locations accessed via its formal parameters. As a result, a good balance between efficiency and precision is made, resulting in ICON that is more powerful than a 1‐callsite‐sensitive analysis and less so than a call‐path‐sensitive analysis (when the recursion cycles in a program are collapsed in all cases). We have compared ICON with FULCRA , a state of the art Andersen's analysis that is context sensitive by acyclic call paths, in Open64 (with recursion cycles collapsed in both cases) using the 16 C/C++ benchmarks in SPEC2000 (totalling 600 KLOC) and 5 C applications (totalling 2.1 MLOC). Our results demonstrate scalability of ICON and lack of scalability of FULCRA . FULCRA spends over 2 h in analysing SPEC2000 and fails to run to completion within 5 h for two of the five applications tested. In contrast, ICON spends just under 7 min on the 16 benchmarks in SPEC2000 and just under 26 min on the same two applications. For the 19 benchmarks analysable by FULCRA , ICON is nearly as accurate as FULCRA in terms of the quality of the built Static Single Assignment (SSA) form and the precision of the discovered alias information. Copyright © 2013 John Wiley & Sons, Ltd.     

一种面向向量化的动态指针别名分析框架

指针别名分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础.在向量化方法和动态指针别名分析相关研究的基础上,设计了一种面向向量化的动态指针别名分析框架.该框架通过动态插桩和试运行提取指针别名信息,并反馈到向量化阶段指导向量化代码生成.从提取候选别名分析集、插桩及试运行和反馈优化3个方面对整体框架进行分析和研究.该框架基于Open64实现,并以通用测试集GCC-VECT和典型应用进行了实验评估,结果表明,该框架相比静态指针别名分析具有更精确的别名分析结果,该结果能够有效改进向量化程序的加速比.     

Composite decision support by combining cost-benefit and multi-criteria decision analysis

This paper concerns composite decision support based on combining cost-benefit analysis (CBA) with multi-criteria decision analysis (MCDA) for the assessment of economic as well as strategic impacts within transport projects. Specifically a composite model for assessment (COSIMA) is presented as a decision support system (DSS). This COSIMA DSS ensures that the assessment is conducted in a systematic, transparent and explicit way. The modelling principles presented are illuminated with a case study concerning a complex decision problem. The outcome demonstrates the approach as a valuable DSS, and it is concluded that appraisals of large transport projects can be effectively supported using a combination of CBA and MCDA. Finally, perspectives of the future modelling work are given.     

Subroutine Inlining and Bytecode Abstraction to Simplify Static and Dynamic Analysis

In Java bytecode, intra-method subroutines are employed to represent code in “finally” blocks. The use of such polymorphic subroutines within a method makes bytecode analysis very difficult. Fortunately, such subroutines can be eliminated through recompilation or inlining. Inlining is the obvious choice since it does not require changing compilers or access to the source code. It also allows transformation of legacy bytecode. However, the combination of nested, non-contiguous subroutines with overlapping exception handlers poses a difficult challenge. This paper presents an algorithm that successfully solves all these problems without producing superfluous instructions. Furthermore, inlining can be combined with bytecode simplification, using abstract bytecode. We show how this abstration is extended to the full set of instructions and how it simplifies static and dynamic analysis.     

Selective conjunction of context‐sensitivity and octagon domain toward scalable and precise global static analysis

We present a practical technique for achieving a scalable and precise global static analysis by selectively applying context‐sensitivity and the octagon relational domain. For precise analysis, context‐sensitivity and relational analysis are key properties, but it has been hard to practically combine both of them. Our approach turns on those precision improvement features only when the analysis is likely to improve the precision to resolve given queries. The guidance comes from an impact pre‐analysis that estimates the impact of a fully context‐sensitive and relational octagon analysis. We designed a cost‐effective pre‐analysis and implemented this method in a realistic octagon analysis for full C. The experimental results show that our approach proves eight times more queries, while saving the time cost by 73.1% compared with a partially relational octagon analysis enabled by a syntactic heuristic. Copyright © 2017 John Wiley & Sons, Ltd.     

基于静态分析技术的源代码安全检测模型*

介绍了当前主流的静态代码分析技术,在分析讨论其优缺点的基础上提出了一种新的静态代码检测模型。该模型结合了当前成熟的静态分析技术,并借鉴了编译器中数据流和控制流分析的思想,获取上下文关联的数据信息,从而更加准确地分析代码中存在的安全问题。     

call图与基于call图的相关分析

ｃａｌｌ图用来反映程序中过程之间的调用关系，在程序分析和程序转换中起着重要的作用。本文首先讨论了简单情形下ｃａｌｌ图的构造算法，然后提出了过程向量及其映射函数的概念，从而设计出一种针对允许过程作为参数时ｃａｌｌ图的构造算法，并对该算法进行了详细的分析，其时间复杂度为Ｏ。本文最后讨论并分析了基于ｃａｌｌ图的程序相关分析方法。     

源代码分析注释的质量评价框架

在如今的软件开发中, 开源软件的使用越来越普遍, 但是对大型开源软件的理解和维护仍然是一项复杂的工作. 开源软件通常缺乏完善的文档和注释, 想要完整的理解开源系统难度较大, 研究界产生了一种通过分析大型开源软件的源代码, 进而深入理解系统, 发现和修复系统漏洞的软件分析型任务. 源代码分析注释是软件分析型任务的一项重要产出, 它是一种以注释形式存在的细粒度代码分析报告, 数量庞大, 难以快速做出质量评价. 在传统的软件质量评价中, 对注释的评价通常局限于覆盖度和文本长度, 不能满足源代码分析注释质量评价的要求. 为了更好的评价源代码分析注释的质量, 本文结合现有的对代码注释质量评价的研究以及信息质量领域的评价方法, 提出了一种综合考虑客观质量属性和主观质量属性的质量评价框架. 结合实际的项目数据分析, 本文的方法可以更有效的检测出注释中的冗余以及无关内容, 发现相关质量问题, 从而对源代码分析注释进行更全面的质量评价.     

二进制代码安全分析综述

近几十年来,计算机硬件性能和软件规模技术已不同以往,其承载了人类社会生活生产的方方面面.计算机技术的飞速发展,也带来了人们对程序安全问题的关注.由于市面上存在着较多的遗留软件,这些软件无人维护且缺乏源代码支持,其安全性令人担忧,而二进制分析技术被用来解决该类软件问题.二进制分析技术根据其检测方式不同可分为:基于静态的二进制代码分析技术、基于动态的二进制代码分析技术和动静态混合的二进制代码分析技术.本文调研了近年来的二进制代码安全分析领域上相关研究,分别详细阐述了这3类技术中的主要方法,并对其关键技术进行详细介绍.     

动态指令流差分分析在恶意软件分析中的应用*

针对静态分析方法已不能满足安全分析的需求,而传统的动态分析技术不能快速定位关键信息,且分析效率不高,提出了一种动态指令流差分分析技术,描述了差分分析模型和分析方法。该分析技术能够高速有效地分析恶意软件的关键数据,识别加密算法,分析混淆代码的功能模块和数据扩散情况。通过实验对其可行性和高效性进行了验证。     

Taxonomy-driven lumping for sequence mining

Given a taxonomy of events and a dataset of sequences of these events, we study the problem of finding efficient and effective ways to produce a compact representation of the sequences. We model sequences with Markov models whose states correspond to nodes in the provided taxonomy, and each state represents the events in the subtree under the corresponding node. By lumping observed events to states that correspond to internal nodes in the taxonomy, we allow more compact models that are easier to understand and visualize, at the expense of a decrease in the data likelihood. We formally define and characterize our problem, and we propose a scalable search method for finding a good trade-off between two conflicting goals: maximizing the data likelihood, and minimizing the model complexity. We implement these ideas in Taxomo, a taxonomy-driven modeler, which we apply in two different domains, query-log mining and mining of moving-object trajectories. The empirical evaluation confirms the feasibility and usefulness of our approach.     

C程序中的内存泄漏机制分析与检测方法设计

C语言作为安全关键软件的主要实现语言,其存在的内存泄漏缺陷具有很高的隐蔽性和危害性,如何保证内存泄漏检测的准确性和高效性是一大挑战。静态分析具有直接分析源码、能够较早发现软件错误,从而降低修复代价的优势。基于静态分析技术,提出了一种基于路径敏感的值流分析的内存泄漏检测方法,首先进行指针分析生成精确指向信息;然后基于指向信息构建值流约束,执行可达性分析以识别程序中的泄漏路径;最后借助指针与内存地址的有效生命周期进行验证。在典型基准C程序上的实验结果分析表明,本文方法与现有技术相比在效率和精度上都具有一定优势。