数组越界的故障模型及其检测方法研究

数组越界是C程序中的常见故障，该类故障可能造成系统的崩溃。首先针对常见的数组越界故障进行了分析，提出了检测数组越界的判定准则，建立了故障模型。根据该故障模型，采用程序控制流图和路径条件，并结合静态分析思想，给出了可有效地检测出程序中存在的数组越界故障的方法。最后通过实例分析了该方法的应用过程。     

面向Android应用的静态污点分析结果的正确性验证

应用静态污点分析检测Android应用的隐私泄露漏洞会产生许多虚警，为此提出一种上下文敏感、路径敏感和域敏感的半自动程序分析方法，仅需遍历少量执行路径即可判定漏洞是否虚警。首先，运行插桩后的应用来获得一条覆盖Source和Sink的种子Trace。然后，应用基于Trace的污点分析方法来验证Trace中是否存在污点传播路径，是则表明漏洞真实存在；否则进一步收集Trace的条件集合和污点信息，结合活变量分析和基于条件反转的程序变换方法设计约束选择策略，以删除大部分与污点传播无关的可执行路径。最后，遍历剩余执行路径并分析相应Trace来验证漏洞是否虚警。基于FlowDroid实现原型系统，对DroidBench的75个应用和10个真实应用进行验证，每个应用平均仅需遍历15.09%的路径，虚警率平均降低58.17%。实验结果表明该方法可以较高效地减少静态分析结果的虚警。     

基于XML的面向二进制漏洞模式形式化描述研究

研究人员通过深入分析大量已公开漏洞的触发成因,将存在安全缺陷的代码抽象为漏洞模式。二进制静态漏洞挖掘技术的核心思想,就是在对二进制程序反汇编得到汇编代码的基础上,以漏洞模式为指导进行安全缺陷检测。文章对缓冲区溢出漏洞、数组越界漏洞、写污点值到污点地址漏洞模式进行了总结,并使用XML对漏洞模式作了形式化描述。     

关于指针错误使用带来的问题——数组越界

该文从指针在C语言中的作用入题,介绍了指针使用过程中常见的几种错误,并提出了改进方法。然后针对指针与数组,总体介绍了它们之间的联系与转换,并详细描述了数组越界的两类错误,最后我们经过详细分析,模拟出一种对数组下标是否越界的检测方法。     

论C语言系统的不完备性

在C语言中,从键盘或磁盘文件输入一个浮点型数据赋给用变量作下标的多维浮点数组或含有浮点成员的结构体数组时,就会出现问题。这是一个完备的编程语言所不应该有的现象。 (1)编一个程序,实现从键盘上输入10个浮点型数据赋给多维浮点数组。     

C程序数组越界的运行时验证技术研究与实现

缓存区溢出能引起非常严重的安全问题,对网络和分布式系统（如机群,网格,P2P系统等）构成严重威胁。数组越界在缓存区溢出中占据重要位置,如何检测数组越界错误是一个重要且极具意义的课题。针对该课题,给出一种对C语言数组越界进行运行时验证的方法。分析了数组越界的错误类型,根据这些类型分别研究了数组越界的运行时验证的思想;设计了基于程序插桩进行数组越界动态检测的算法,给出了该方法基于开源编译器Clang的具体实现;用实验证明了该方法是切实可行并且有效的。     

基于条件范围约束的越界访问检测方法

程序执行时的越界访问将导致异常的行为,已有的越界检测方法存在效率低或精度不高的缺点．分两步检测程序中的越界访问语句：在约束产生阶段,提出一个流敏感、过程间的约束状态产生算法,为每条语句建立一个范围约束集合和值约束集合;在约束求解阶段,利用线性规划计算程序访问的内存大小和偏移量,报告可能的越界访问漏洞．实验表明,检测效率明显高于路径敏感的范围分析方法,而平均检测精度高于80％．     

一种面向Trace与漏洞验证的污点分析方法

静态分析方法被广泛用于Android应用的隐私泄露检测,其以(Source,Sink)对形式检测潜在漏洞,但同时会产生大量虚警。针对该问题,提出一种上下文敏感和域敏感的污点分析方法。对污点传播的操作语义和一致性约束进行形式化定义,保证污点传播的语义正确性,同时分析插桩运行Android应用后产生的Trace片段,验证漏洞是否存在虚警。基于Soot实现原型系统并对DroidBench数据集中的70个应用进行分析,实验结果表明,该方法可成功验证4个虚警并发现8个漏报,表明其能有效判断静态分析结果的正确性。     

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

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

数组越界的静态分析

软件测试分为静态测试和动态测试,而数组越界是静态测试中最常见的问题之一,并且其带来的危害巨大,甚至导致软件系统崩溃。根据数组越界的现象及特点,详细描述了数组越界的定义和种类,给出了数组越界产生的条件及防范技巧,并对检测方法及工具进行比较分析,从而更好地实现软件测试。     

Static Checking of Array Index Out-of-Bounds Defects in C Programs Based on Taint Analysis

During the rapid development of mobile computing, IoT, cloud computing, artificial intelligence, etc., many new programming languages and compilers are emerging. Nevertheless, C/C++ is still one of the most popular languages, and the array is one of the most important data structures of C language. It is necessary to check whether the index is within the boundary of the array when it is used to access the element of an array in a program. Otherwise, array index out-of-bounds will happen unexpectedly. When array index out-of-bounds defects are in programs, some serious errors may occur during execution, such as system crash. It is even worse that array index out-of-bounds defects open the doors for attackers to take control of the server and execute arbitrary malicious codes by carefully constructing input and intercepting the control flow of the programs. Existing static methods for array boundary checking cannot achieve high accuracy and deal with complex constraints and expressions, leading to massive false positives. In addition, it will increase the burden of developers. In this study, a static checking method is proposed based on taint analysis. First, a flow-sensitive, context-sensitive, and on-demand pointer analysis is proposed to analyze the range of array length. Then, an on-demand taint analysis is performed for all array indices and array length expressions. Finally, the rules are defined for checking array index out-of-bounds defects and the checking is realized based on backward data flow analysis. During the analysis, in light of complex constraints and expressions, it is proposed to check the satisfiability of the conditions by invoking the constraint solver. If none statement for avoiding array index out-of-bounds is found in the program, an array index out-of-bound warning will be reported. An automatic static analysis tool, Carraybound, has been implemented, and the experimental results show that Carraybound can work effectively and efficiently.     

Dependently typed array programs don’t go wrong

The array programming paradigm adopts multidimensional arrays as the fundamental data structures of computation. Array operations process entire arrays instead of just single elements. This makes array programs highly expressive and introduces data parallelism in a natural way. Array programming imposes non-trivial structural constraints on ranks, shapes, and element values of arrays. A prominent example where such constraints are violated are out-of-bound array accesses. Usually, such constraints are enforced by means of run time checks. Both the run time overhead inflicted by dynamic constraint checking and the uncertainty of proper program evaluation are undesirable.We propose a novel type system for array programs based on dependent types. Our type system makes dynamic constraint checks obsolete and guarantees orderly evaluation of well-typed programs. We employ integer vectors of statically unknown length to index array types. We also show how constraints on these vectors are resolved using a suitable reduction to integer scalars. Our presentation is based on a functional array calculus that captures the essence of the paradigm without the legacy and obfuscation of a fully-fledged array programming language.     

基于污点指针的二进制代码缺陷检测

污点指针严重影响二进制代码数据流和控制流的安全。为此,提出一种二进制代码缺陷检测方法。引入指针污点传播规则,结合路径约束条件和边界约束条件得到缺陷引发条件,构造能够引发4类污点指针代码缺陷的输入数据。在Linux系统下实现ELF二进制代码缺陷检测工具,测试结果表明,该方法能降低测试用例生成数量,并发现Linux系统工具的1个虚函数调用控制缺陷和2个指针内存破坏缺陷。     

Static validation of WS-CDL documents

This paper presents an approach to validate WS-CDL documents statically. To deal with those constraints appeared in CDL documents, which cannot be captured by its meta model (XML Schema) totally, we design a machine-based constraint language based on B Method, which uses abstract machines to represent the constraints of the relations among XML nodes. After modelling the constraints, the corresponding checking algorithm can be designed to implement the static validation of CDL documents. Meanwhile, the checking algorithm is integrated into the WS-CDL editor plug-in for Eclipse project. The case studies show that our approach is effective for real examples in practice.     

Practical type checking of functions defined on Context-Free languages

A type checking method for the functional language LFC is presented. A distinct feature of LFC is that it uses Context-Free (CF) languages as data types to represent compound data structures. This makes LFC a dynamically typed language. To improve efficiency, a practical type checking method is presented, which consists of both static and dynamic type checking. Although the inclusion relation of CF languages is not decidable, a special subset of the relation is decidable, i.e., the sentential form relation, which can be statically checked. Moreover, most of the expressions in actual LFC programs appear to satisfy this relation according to the statistic data of experiments. So, despite that the static type checking is not complete, it undertakes most of the type checking task. Consequently the run-time efficiency is effectively improved. Another feature of the type checking is that it converts the expressions with implicit structures to structured representation. Structure reconstruction technique is pr     

Validation of array accesses: integration of flow analysis and program verification techniques

A program that accesses an out-of-bound array element can cause unexpected behaviour that is unacceptable to safety-critical or security-critical systems. Two traditional compile-time approaches to array bound checking are flow analysis and program verification. This paper presents a new approach, IFV, that integrates flow analysis and program verification techniques. IFV is generally about as effective as program verification yet runs in about the same time as flow analysis. Its typical runtime is proportional to the product of the program size and the number of declared variables. IFV matches loops to templates, which represent commonly occurring loop patterns, to discover loop invariants automatically, which it then uses to strengthen flow analysis. With only seven templates, it handles many common array-access patterns. Patterns not verified by flow analysis are processed with verification techniques entirely automatically. This paper also describes a prototype IFV system that performs compile-time array bound checking for programs in a subset of C. © 1997 John Wiley & Sons, Ltd.     

Array bounds check elimination in the context of deoptimization

Whenever an array element is accessed, Java virtual machines execute a compare instruction to ensure that the index value is within the valid bounds. This reduces the execution speed of Java programs. Array bounds check elimination identifies situations in which such checks are redundant and can be removed. We present an array bounds check elimination algorithm for the Java HotSpot? VM based on static analysis in the just-in-time compiler.The algorithm works on an intermediate representation in static single assignment form and maintains conditions for index expressions. It fully removes bounds checks if it can be proven that they never fail. Whenever possible, it moves bounds checks out of loops. The static number of checks remains the same, but a check inside a loop is likely to be executed more often. If such a check fails, the executing program falls back to interpreted mode, avoiding the problem that an exception is thrown at the wrong place.The evaluation shows a speedup near to the theoretical maximum for the scientific SciMark benchmark suite and also significant improvements for some Java Grande benchmarks. The algorithm slightly increases the execution speed for the SPECjvm98 benchmark suite. The evaluation of the DaCapo benchmarks shows that array bounds checks do not have a significant impact on the performance of object-oriented applications.     

C程序非法计算缺陷的静态检测

为实现基于静态分析技术自动的检测C程序中的非法计算缺陷,提出了一种基于区域内存模型进行非法计算缺陷检测的方法。对C程序中的非法计算缺陷操作归纳总结出其受限集,以对相应运算进行约束;通过抽象的区域内存模型表示实际的内存存储,实现了基于抽象内存区域内存模型的数据流分析;基于数据流分析的结果,判定C程序中的受限操作是否违背受限集的约束,以实现非法计算缺陷的检测。5个实际工程的检测结果分析表明,该方法可有效地检测出C程序的各类非法计算缺陷。     

基于访问控制的动态着色技术在攻击检测中的研究

内存腐烂攻击在软件安全攻击中占据着较大的比重。近来,动态着色技术得到了越来越多的关注,这种技术通过在访问内存时检测指针的完整性来抵御攻击。然而,存在一类可以绕过指针完整性检查的策略来进行攻击的实例,比如数组的越界访问攻击。提出了一种基于动态着色跟踪分析的方法来解决这类已有着色技术不能检测的问题。其思想是,借助于内存访问控制的思路,首先像已有的动态着色技术那样,在内存访问时对指针进行完整性检查,然后检查指针将要访问的内存区域是否处于指针合理的访问范围之内。原型系统是基于Valgrind的,并不需要源码,因此可以用于很多商业软件。初步实验验证结果表明,该方法可以有效地检测出很多类型的攻击,系统的性能损耗接近于Memcheck这种常用的内存错误检测工具。