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

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

基于对象的C程序边界安全检测改进技术

C语言对内存操作不进行边界安全检测,这使C程序具有高执行效率,但也产生各种安全问题,例如数组越界、指针访问越界、C库函数的非法操作等。基于对象的运行时验证技术能实时监测程序的运行行为,自动找出程序中存在的漏洞。在原有基于对象技术的基础上,改进多维数组和结构体变量的地址范围记录方式,用2次地址查询操作检测指针访问,用平衡二叉树优化存储结构。实验结果表明,改进的方法优于传统的基于对象技术。     

基于污点分析的数组越界缺陷的静态检测方法

随着移动计算、物联网、云计算、人工智能等领域的飞速发展,也涌现出了很多新的编程语言和编译器,但是C/C++语言依旧是最受欢迎的编程语言之一,而数组是C语言最重要的数据结构之一.当在程序中通过数组下标访问数组元素时,必须确保该下标在该数组的边界之内,否则就会导致数组越界.程序中的数组越界缺陷会使得程序在运行时导致系统崩溃,甚至使攻击者可以截取控制流以执行任意恶意代码.当前针对数组越界的静态检查方法无法达到高精度的分析,尤其是无法处理复杂约束和表达式,过多的误报额外增加了开发者的负担.因此,提出了一种基于污点分析的数组越界的静态检测方法.首先,提出流敏感、上下文敏感的按需指针分析方法,实现数组长度区间分析.然后,提出按需污点分析方法,实现数组下标和数组长度污染情况的计算.最后,定义数组越界缺陷判定规则,提出使用后向数据流分析方法,检测数组下标是否越界.在进行数组越界检测的过程中,为了处理程序中的复杂约束和表达式,在分析过程中将调用约束求解器来判断约束的可满足性.如果没有发现相应的语句,则报告数组越界缺陷警报.同时,实现了自动静态分析工具Carraybound,并通过实验展示了方法的有效性.     

基于Coq的软件安全性验证

针对数组越界、空指针应用和缓冲区溢出三类威胁软件安全的不规范操作,提出了一种基于Coq验证上述三类操作的形式化方法。首先编写三类安全问题的程序实例,并采用形式化方法进行标注;其次运用Frama-C和Why工具对标注程序进行解析,生成需要证明的定理;最后基于Coq集成开发环境证明定理,实现安全问题的验证。结果表明,该方法有效验证了软件安全中的三类问题,为形式化方法在软件安全性验证方面的应用奠定了基础。     

基于CPA的抽象解释分析方法研究

安全关键领域中,如何保证软件安全性已经成为了一个广受关注的重要课题。确保程序中没有运行时错误,对于软件安全性的保证十分重要。基于抽象解释的静态分析方法对程序语义进行抽象,是验证运行时错误最合适的形式化方法之一。可配置程序分析（configurable program analysis,CPA）是一种适合多种静态分析方法的通用分析框架。本文使用CPA对抽象解释分析方法进行建模,给出了使用基于CPA的抽象解释方法验证程序中的运行时错误的验证流程,并用实例说明该验证方法的有效性。为程序中运行时错误的自动化分析和验证提供了一种可行方案。     

缓存区溢出研究与发展

为检测出缓存区溢出的发生和预防攻击者利用缓存区溢出漏洞进行攻击,研究人员提出了各种各样的检测和预防技术.首先介绍了缓存区溢出的四种攻击方式,将主流的缓存区溢出检测和预防技术进行了分类,介绍了每一类的原理、发展历程和优缺点;然后对这些检测和预防技术进行了综合讨论;最后对缓存区溢出检测和预防技术的未来发展趋势进行了分析与预测.     

数组越界的静态分析

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

基于整型区间集的数组越界静态自动测试方法研究

数组越界是软件中普遍存在的一种故障类型，并对软件安全造成了潜在的威胁．传统的故障检测使用程序插装的方法，并相应的以编译优化技术来排除掉多余的数组边界检查．这种检测方法不仅降低了程序运行效率，增加了开销，而且往往不能对故障进行彻底的测试，容易造成漏报．本文在对程序进行静态分析的基础上，通过引入区间概念，建立了整型区间集和数组区间集，进而给出了数组越界的故障模型，模型的建立对软件故障进行了规范．本文随后给出了故障检测算法，最后给出了实验．结果表明这种方法比以往的测试方法具有更强的故障检测能力．     

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

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

数组越界的静态测试分析

给出了一种静态分析方法，静态分析的主要优点就是在程序运行之前就可以对程序故障进行定位。文章首先针对数组越界错误类型进行了分析，介绍了软件测试的一些基本概念，给出了这类错误的静态分析方法，并给出了相应的算法，而后给出了测试系统设计和开发，最后给出了软件测试的实验结果和分析。     

Hardware/software optimization for array & pointer boundary checking against buffer overflow attacks

Malicious intrusions by buffer overflow attacks cause serious security problems and pose serious threats for networks and distributed systems such as clusters, Grids and P2P systems. Array & pointer boundary checking is one of the most effective approaches for defending against buffer overflow attacks. However, a big performance overhead may occur after boundary checking is applied. Typically, it may cause 2–5 times slowdown [T.M. Austin, E.B. Scott, S.S. Gurindar, Efficient detection of all pointer and array access errors, in: Proceedings of the ACM SIGPLAN ’94 Conference on Programming Language Design and Implementation, 1994, pp. 290–301; R.W.M. Jones, P.H.J. Kelly, Backwards-compatible bounds checking for arrays and pointers in c programs, in: The Third International Workshop on Automated and Algorithmic Debugging, 1997, pp. 13–26]. In this paper, we propose a hardware/software method to optimize the performance of array & pointer boundary checking by designing a special boundary checking instruction. The experimental results show that our method can effectively reduce the overhead of array & pointer boundary checking.     

可能性测度下的CTL符号化模型检测

随着系统复杂性的增加,系统中的不确定信息亟待处理,状态爆炸问题也越来越严峻,现有的模型检测技术已不能完全适用于复杂系统的验证。 对可能性测度下CTL符号化模型检测进行了研究。首先用多终端二值决策图和布尔公式分别描述系统模型和待验证性质,然后再对系统模型进行归一化和简化,最后利用不动点计算完成系统验证。该研究是对可能性测度下的模型检测技术和符号化模型检测技术的整合,不但能处理系统的不确定信息,而且保持了符号化模型检测对计算时空要求低的优点,对于复杂系统模型检测具有重要意义。     

Analysis and verification of real-time systems using quantitative symbolic algorithms

The task of checking if a computer system satisfies its timing specifications is extremely important. These systems are often used in critical applications where failure to meet a deadline can have serious or even fatal consequences. This paper presents an efficient method for performing this verification task. In the proposed method a real-time system is modeled by a state-transition graph represented by binary decision diagrams. Efficient symbolic algorithms exhaustively explore the state space to determine whether the system satisfies a given specification. In addition, our approach computes quantitative timing information such as minimum and maximum time delays between given events. These results provide insight into the behavior of the system and assist in the determination of its temporal correctness. The technique evaluates how well the system works or how seriously it fails, as opposed to only whether it works or not. Based on these techniques a verification tool called Verus has been constructed. It has been used in the verification of several industrial real-time systems such as the robotics system described below. This demonstrates that the method proposed is efficient enough to be used in real-world designs. The examples verified show how the information produced can assist in designing more efficient and reliable real-time systems.     

Computation of Sharp Rigorous Componentwise Error Bounds for the Approximate Solutions of Systems of Linear Equations

This paper is concerned with the problem of verifying the accuracy of approximate solutions of systems of linear equations. Recently, fast algorithms for calculating guaranteed error bounds of computed solutions of systems of linear equations have been proposed using the rounding mode controlled verification method and the residual iterative verification method. In this paper, a new verification method for systems of linear equations is proposed. Using this verification method, componentwise verified error bounds of approximate solutions of systems of linear equations can be calculated. Numerical results are presented to illustrate that it is possible to get very sharp error bounds of computed solutions of systems of linear equations whose coefficient matrices are symmetric and positive definite.     

基于不可满足核的近似逼近可达性分析

近年来,形式化验证技术受到了越来越多的关注,它在保障安全关键领域系统的安全性和正确性方面发挥着重要的作用.模型检测作为形式化验证中自动化程度较高的分支,具有十分广阔的发展前景.本文中我们研究并提出了一种新的模型检测技术,可以有效地对迁移系统进行模型检测,包括不安全性检测和证明安全性.与现有的模型检测算法不同,我们提出的这种方法——基于不可满足核（unsatisfiable core,UC）的近似逼近可达性分析（UC-based approximate incremental reachability,UAIR）,主要利用不可满足核来求解一系列的候选安全不变式直至生成最终的不变式,以此来实现安全性证明和不安全性检测（漏洞查找）.在基于SAT求解器的符号模型检测中,我们使用由可满足性求解器得到的UC构造候选安全不变式,如果迁移系统本身是安全的,我们得到的初始不变式只是安全不变式的一个近似.然后,我们在检查安全性的同时,逐步改进候选安全不变式,直到找到一个真正的不变式,证明系统是安全的;如果系统是不安全的,我们的方法最终可以找到一个反例证明系统是不安全的.作为一种全新的方法,我们利用不可满足核进行安全性模型检测,取得了相当好的效果.众所周知,模型检测领域没有绝对最好的方法,尽管我们的方法在基准的可解数量上无法超越当前的成熟方法例如IC3、CAR等,但是我们的方法却可以解出3个其他方法都无法解出的案例,相信本方法可以作为模型检测工具集很有价值的补充.     

并发系统的安全性与活性的验证方法

网络环境下的分布式系统是典型的并发系统。安全性和活性是并发系统最为关注和需要保证的两个主要性质。然而在并发系统建模和形式化验证时,面临着描述繁琐、复杂和难以理解的问题,特别是当并发系统的规模（并发进程数目）较大时其性质验证时的效率问题更是严重阻碍了并发系统模型检测与验证技术的应用。将组合可达性分析和标号迁移系统的模块化思想与模型验证技术相结合,提出了一套有效的性质验证方法。论证、分析了三个并发系统安全性和活性验证定理,据此导出了并发系统的安全性与活性验证的有效算法。并通过一个简单实例,对算法有效性进行了初步验证。     

Verification of consensus algorithms using satisfiability solving

Consensus is at the heart of fault-tolerant distributed computing systems. Much research has been devoted to developing algorithms for this particular problem. This paper presents a semi-automatic verification approach for asynchronous consensus algorithms, aiming at facilitating their development. Our approach uses model checking, a widely practiced verification method based on state traversal. The challenge here is that the state space of these algorithms is huge, often infinite, thus making model checking infeasible. The proposed approach addresses this difficulty by reducing the verification problem to small model checking problems that involve only single phases of algorithm execution. Because a phase consists of a small, finite number of rounds, bounded model checking, a technique using satisfiability solving, can be effectively used to solve these problems. The proposed approach allows us to model check several consensus algorithms up to around 10 processes.     

基于备份控制流信息的缓冲区溢出监测技术

C/C++在提供灵活的使用方式和高效目标码的同时,由于缺少边界检查机制,缓冲区溢出成为C/C++程序面临的一种严重的攻击威胁。给出了一种缓冲区溢出攻击的动态防护方法。使用在库中声明的数组来备份函数的控制流信息,包括返回地址和栈帧指针,来动态监测非法的篡改行为。该方法可以对缓冲区溢出攻击中的直接攻击和间接攻击均有效防护。通过RIPE基准平台和两道实际应用的测试以及理论比较表明该方法的有效性。     

基于模拟关系的精化检测方法

精化检测是一种重要的形式化验证方法,将系统实现和性质规约用相同形式化语言进行建模,如能证明两者间存在某种精化关系且该关系能够维持性质,可得出系统实现满足性质规约.为验证不同类型的系统性质, traces、stable failures和failures-divergence精化检测方法已被提出.精化检测算法依赖于子集构造,因而其面临状态空间爆炸问题.近年来,已有学者针对NFA语言包含问题提出了基于模拟关系的状态空间消减方法,大大提高了算法性能,且该方法能直接用于traces精化检测.在此基础上,本文提出了基于模拟关系的stable failures和failures-divergence精化检测方法.此外,本文还将精化检测扩展到了时间系统的验证中,提出了基于模拟关系的时间自动机traces精化检测方法.实验结果表明,基于模拟关系的算法效率有很大提高.