• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 25
    • 下载费用:30 金币  

    重庆时时彩组六杀码技巧: 数组越界错误的自动检测和校正方法.pdf

    关 键 词:
    数组 越界 错误 自动检测 校正 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    摘要
    申请专利号:

    CN201410022323.0

    申请日:

    2014.01.17

    公开号:

    CN103778061A

    公开日:

    2014.05.07

    当前法律状态:

    授权

    有效性:

    有权

    法律详情: 授权|||实质审查的生效IPC(主分类):G06F 11/36申请日:20140117|||公开
    IPC分类号: G06F11/36 主分类号: G06F11/36
    申请人: 南京航空航天大学
    发明人: 陈哲; 李文明; 黄志球
    地址: 210016 江苏省南京市秦淮区御道街29号
    优先权:
    专利代理机构: 南京经纬专利商标代理有限公司 32200 代理人: 朱小兵;刘谦
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201410022323.0

    授权公告号:

    ||||||

    法律状态公告日:

    2016.08.24|||2014.06.11|||2014.05.07

    法律状态类型:

    授权|||实质审查的生效|||公开

    摘要

    本发明提供一种数组越界错误的自动检测和校正方法,包括:选择待变换的源代码;利用编译器生成源代码的符号表和抽象语法树;遍历抽象语法树,构造指针依赖图,并进行源代码变换计算;在源代码中将需替换的部分源代码进行替换;将按照数组越界检测策略和校正策略生成的函数定义写入变换后源代码的开头部分;将变换后的源代码用原编译器进行编译;把生成的可执行文件部署到目标系统并运行,自动检测和校正数组越界错误,并准确报告错误对应的源代码位置。本发明提供的数组越界错误的自动检测和校正方法具有更准确的错误定位功能,更好的运行时效率和性能,更自动化的运行时错误校正功能。

    权利要求书

    权利要求书
    1.  一种数组越界错误的自动检测和校正方法,其特征在于,包括:
    步骤1、选择待变换的源代码项目目录,或者单个源代码文件;
    步骤2、针对待变换的源代码,利用编译器生成源代码的符号表和抽象语法树;
    步骤3、遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算,其中:所述指针依赖图是一个有向图二元组,所述有向图二元组包括源代码中的指针集合和源代码中的指针依赖关系集合,所述源代码中的指针集合构成指针依赖图中的结点集合,所述源代码中的指针依赖关系集合构成指针依赖图中的有向边集合;
    步骤4、根据步骤3的计算结果,在源代码中将需替换的部分源代码进行替换,生成变换后的源代码,并保存到新项目目录或新文件;
    步骤5、定义数组越界检测策略和校正策略,并将这些策略转化为函数__MNT_CHK_AAV的定义,将按照策略生成的函数__MNT_CHK_AAV的定义写入变换后源代码的开头部分;
    步骤6、将变换后的项目目录或文件用原编译器进行编译,生成目标系统上的可执行文件;
    步骤7、将生成的可执行文件部署到目标系统并运行,当可执行文件运行到已替换或插入的代码段时,将自动检测和校正数组越界错误,并准确报告错误对应的源代码位置。

    2.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于,所述遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算,进一步包括:
    在遍历抽象语法树的过程中,根据当前遍历到的结点s的类型进行如下操作之一:
    向指针依赖图中加入指针依赖关系,
    将数组下标访问表达式和指针访问表达式替换为__MNT_CHK_AAV函数的调用,
    将函数声明、函数定义、函数调用表达式替换为新的表达式。

    3.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于,所述在遍历抽象语法树的过程中,根据当前遍历到的结点s的类型进行如下操作之一: 向指针依赖图中加入指针依赖关系,将数组下标访问表达式和指针访问表达式替换为__MNT_CHK_AAV函数的调用,将函数声明、函数定义、函数调用表达式替换为新的表达式,进一步包括:
    在遍历抽象语法树的过程中,对于当前遍历到的结点s,得到其所在的源文件名filename和代码行号loc,并根据当前遍历到的结点s的类型分别进行如下操作:
    操作1、如果结点s是一个带初始值的指针声明type*p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q,则将指针对(p,q)作为一条边加入指针依赖图;
    操作2、如果结点s是一个指针赋值表达式p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q,则将(p,q)作为一条边加入指针依赖图;
    操作3、如果结点s是一个数组下标表达式p[expr],其中p为指针名或数组名,expr为表达式,则根据p的类型分别进行如下操作:
    操作31、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,p,p+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作32、如果p是所在函数声明的第n个形式参数,则从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作33、如果p是不满足以上操作31、操作32中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作331、如果q是符号表中已定义的一个数组,则从符号表中获取指针p的类 型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,q,q+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作332、如果q是所在函数声明的第n个形式参数,则从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作333、如果q是不满足以上操作331、操作332中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错;
    操作4、如果结点s是一个指针访问表达式*expr,其中expr为表达式,且expr中包含一个支配指针p,则根据p的类型分别进行如下操作:
    操作41、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,p,p+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作42、如果p是所在函数声明的第n个形式参数,则从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作43、如果p是不满足以上操作41、操作42中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作431、如果q是符号表中已定义的一个数组,则从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,q,q+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作432、如果q是所在函数声明的第n个形式参数,则从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作433、如果q是不满足以上操作431、操作432中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错;
    操作5、如果结点s是一个函数声明或函数定义表达式type func(…,type_nexpr_n,…),其中:第n个参数表达式expr_n为type_n类型的数组或指针声明p,省略号…表示其它参数表达式,则将该函数声明或函数定义替换为如下函数:
    type func(…,type_n expr_n,void*__MNT_CHK_AAV_B_n,void*__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个参数表达式的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个参数表达式的结束地址;
    操作6、如果结点s是一个函数调用表达式func(…,expr_n,…),其中:第n个参数表达式expr_n中包含一个支配指针p,省略号…表示其它参数表达式,则根据p的类型分别进行如下操作:
    操作61、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的长度 len,然后将该表达式替换为如下函数调用:func(…,expr_n,p,p+len,…),其中,省略号…表示原来的所有参数表达式,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址;
    操作62、如果p是所在函数声明的第n个形式参数,则将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    操作63、如果p是不满足以上操作61、操作62中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作631、如果q是符号表中已定义的一个数组,则从符号表中获取数组q的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,q,q+len,…),其中,省略号…表示原来的所有参数表达式,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址;
    操作632、如果q是所在函数声明的第n个形式参数,则将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    操作633、如果q是不满足以上操作631、操作632中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错。

    4.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于,所述步骤3进一步包括:
    在指针依赖图中,从p开始沿有向边往前遍历,直到访问到一个没有后继结点的指针q,那么q就是p的最终依赖指针。

    5.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于,所 述步骤3进一步包括:
    支配指针是指决定该表达式指向地址的主要指针变量;
    该表达式的其他部分决定相对于该指针指向地址的偏移量。

    6.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于,所述检测策略包括:
    判断要访问的地址p是否在允许的范围[begin,end)之间,如果超出该范围,则报告数组越界错误。

    7.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于:所述校正策略包括:
    当合法的内存范围为[begin,end),大小为n时,
    如果访问地址p为下越界,则将p和begin之间的偏移量进行模n运算,并被end减后作为映射的合法访问地址;
    如果访问地址p为上越界,则将p和end之间的偏移量进行模n运算,并加上begin作为映射的合法访问地址;
    如果访问地址p在[begin,end)范围内,则不作任何计算。

    8.  如权利要求1所述的数组越界错误的自动检测和校正方法,其特征在于:所述步骤5进一步包括:
    检测策略和校正策略直接通过源代码的方式说明;或者,
    使用特别定义的描述语言来说明,并通过语言自动转化工具自动翻译为源代码。

    说明书

    说明书数组越界错误的自动检测和校正方法
    技术领域
    本发明涉及计算机软件测试和校正技术领域,特别涉及一种数组越界错误的自动检测和校正方法。
    背景技术
    缓冲区溢出是一种非常危险的软件漏洞,并广泛存在于各种应用软件中?;撼迩绯雎┒纯赡艿贾氯砑形斐?、内存访问错误或系统崩溃,也可被黑客用来攻击有价值的软件系统。目前,缓冲区溢出问题已经成为造成软件漏洞的主要原因。例如,根据US-CERT漏洞数据库统计资料可知,在20个最严重的漏洞中,就有11个是由缓冲区溢出引起。尤其对于那些用于控制安全关键工业系统的嵌入式控制软件(例如,飞行控制软件、高速列车控制软件、核电站控制软件等)和安全关键应用软件系统(例如,银行交易软件、网上交易软件等),当因缓冲区溢出漏洞引起软件失效、系统故障或黑客攻击,损失将非常惨重。因此,有效的缓冲区溢出检测和校正技术是软件研发和维护中的重要问题。
    软件中缓冲区的内存分配包括两种方式:静态内存分配和动态内存分配。静态内存分配主要指源代码中变量和数组的定义,而动态内存分配主要指使用malloc等内存管理函数为软件分配的堆空间。通常,不带操作系统或内存管理??榈那度胧焦ひ悼刂葡低巢恢С侄诖娣峙?。因此,在这样的系统中,数组越界访问成为了缓冲区溢出的主要表现形式。也就是说,检测和校正软件中的数组越界错误是避免缓冲区溢出的主要方式。
    目前,现有的检测数组越界错误的方法分为两种类型:静态方法和动态方法。
    静态方法是指通过分析软件设计模型或者源代码来检验错误的方法,而不需要实际运行该软件。除人工代码走查之外,静态方法的一个主流技术是模型检验技术,例如SPIN模型检验器等。模型检验工具一般通过抽象建模,运行验证,生成和分析反例等步骤来检验设计模型的正确性。例如,业内曾经使用SPIN模型检验器对某型国 产飞机的飞行控制系统的缓冲区控制??榈纳杓颇P徒辛搜橹?,准确地找出了由??榧涓丛咏换バ形鸬氖樵浇绱砦?。模型检验技术的优点在于,可以对软件所有可能的行为进行穷举搜索,确保结果的完备性。然而,该技术的不足之处在于:1、由于模型检验技术本身的计算复杂性是PSPACE完全的,因此它与生俱来的状态爆炸问题使得该技术很难直接被应用于较大规模软件的验证,例如超过10000行代码的软件;2、由于模型检验技术通常是对软件系统抽象出来的设计模型进行验证,而不是全部源代码,所以无法确保该软件的实际实现是正确的,即无法确保源代码的正确性。
    动态方法是指通过运行软件,并在软件运行过程中检测错误的方法。动态方法的一个主流技术是软件测试技术。软件测试工具一般通过编译源代码、运行待测试软件等步骤,在软件运行过程中根据设计的测试用例注入测试数据,通过对软件的输出进行分析(例如,与测试用例的预计输出进行对比),来观察软件运行是否正确,检测软件是否存在错误。软件测试技术的优点在于,有一定的自动化功能,可以进行测试用例管理、批量测试和回归测试。然而,该技术的不足之处在于:1、由于不直接面对源代码,无法准确定位导致错误发生的源代码位置;2、由于错误定位不准确,为软件的开发调试和校正造成了障碍。
    另一种有效的动态方法是将软件在一个虚拟机上运行,该虚拟机可以模拟内存管理???,从而检测软件中的数组越界错误。例如JAVA虚拟机就是一个典型的代表。虚拟机技术的优点在于,由于整个软件都处于被监控的状态,因此检测结果非常准确。然而,该技术的不足之处在于:1、由于虚拟机对软件的解释执行,使得软件运行负载过大,以至于软件效率和性能降低非常明显;2、对于嵌入式安全关键工业控制系统,由于高实时性和内存资源受限的要求,这样的效率和性能降低往往不能被接受,因此这种方法并不实用。
    在检测到错误的存在后,就需要对错误进行校正,比如修改源代码。对于校正数组越界访问错误,常用的方法是人工调试和校正。也就是说,在软件测试阶段,根据软件测试工具的测试报告,由程序员使用代码调试工具,人工分析源代码的执行过程来定位错误。这一方法的优点是容易操作,不需要使用额外的工具。然而,该技术的不足之处在于:1、当源代码规模较大或者功能较为复杂,程序员不一定能准确定位错误在源代码中的位置,从而无法正确地修改源代码;2、当软件已经被部署到目标平台上,在实际运行过程中出现的数组越界访问错误无法通过这种方法进行校正,因 此可能会引起软件失效、系统故障或黑客攻击。
    因此,有必要提供一种新的数组越界错误的自动检测和校正方法,以实现更准确的错误定位功能,更好的运行时效率和性能,以及更自动化的运行时错误校正功能,从而克服现有的检测数组越界错误的方法中存在的技术问题。
    发明内容
    为了克服上述已有技术存在的不足,本发明的目的旨在提供一种新的检测和校正数组越界错误的方法,通过使用源代码变换技术,将源代码变换为带有自动检测和校正功能的源代码,使得可以在软件运行过程中自动检测和校正软件中数组越界错误,以实现更准确的错误定位功能,更好的运行时效率和性能,以及更自动化的运行时错误校正功能,从而克服现有的检测数组越界错误的方法中存在的技术问题。
    本发明提供一种数组越界错误的自动检测和校正方法,其特征在于,包括:步骤1、选择待变换的源代码项目目录,或者单个源代码文件;步骤2、针对待变换的源代码,利用编译器生成源代码的符号表和抽象语法树;步骤3、遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算;步骤4、根据步骤3的计算结果,在源代码中将需替换的部分源代码进行替换,生成变换后的源代码,并保存到新项目目录或新文件;步骤5、定义数组越界检测策略和校正策略,并将这些策略转化为函数定义,将按照策略生成的函数定义写入变换后源代码的开头部分;步骤6、将变换后的项目目录或文件用原编译器进行编译,生成目标系统上的可执行文件;步骤7、把生成的可执行文件部署到目标系统并运行,当可执行文件运行到那些替换或插入的代码段时,将自动检测和校正数组越界错误,并准确报告错误对应的源代码位置。
    进一步地,所述遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算,包括:指针依赖图是一个有向图二元组(V,E),其中:V是源代码中的指针集合并构成指针依赖图中的结点集合,E是源代码中的指针依赖关系集合并构成指针依赖图中的有向边集合;在遍历抽象语法树的过程中,根据当前遍历到的结点s的类型进行如下操作之一:向指针依赖图中加入指针依赖关系,将数组下标访问表达式和指针访问表达式替换为函数调用,将函数声明、函数定义、函数调用表达式替换为新的表达式。
    进一步地,所述在遍历抽象语法树的过程中,根据当前遍历到的结点s的类型进 行如下操作之一:向指针依赖图中加入指针依赖关系,将数组下标访问表达式和指针访问表达式替换为函数调用,将函数声明、函数定义、函数调用表达式替换为新的表达式,包括:在遍历抽象语法树的过程中,对于当前遍历到的结点s,得到其所在的源文件名filename和代码行号loc,并根据结点s的类型分别进行如下操作:
    操作1、如果结点s是一个带初始值的指针声明type*p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q,则将(p,q)作为一条边加入指针依赖图;
    操作2、如果结点s是一个指针赋值表达式p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q,则将(p,q)作为一条边加入指针依赖图;
    操作3、如果结点s是一个数组下标表达式p[expr],其中p为指针名或数组名,expr为表达式,则根据p的类型分别进行如下操作:
    操作31、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,p,p+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作32、如果p是所在函数声明的第n个形式参数,则从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作33、如果p是不满足以上操作31、操作32中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作331、如果q是符号表中已定义的一个数组,则从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,q,q+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作332、如果q是所在函数声明的第n个形式参数,则从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作333、如果q是不满足以上操作331、操作332中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错;
    操作4、如果结点s是一个指针访问表达式*expr,其中expr为表达式,且expr中包含一个支配指针p,则根据p的类型分别进行如下操作:
    操作41、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,p,p+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作42、如果p是所在函数声明的第n个形式参数,则从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作43、如果p是不满足以上操作41、操作42中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未 赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作431、如果q是符号表中已定义的一个数组,则从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,q,q+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作432、如果q是所在函数声明的第n个形式参数,则从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    操作433、如果q是不满足以上操作431、操作432中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错;
    操作5、如果结点s是一个函数声明或函数定义表达式type func(…,type_n expr_n,…),其中:第n个参数表达式expr_n为type_n类型的数组或指针声明p,省略号…表示其它参数表达式,则将该函数声明或函数定义替换为如下函数:
    type func(…,type_n expr_n,void*__MNT_CHK_AAV_B_n,void*__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个参数表达式的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个参数表达式的结束地址;
    操作6、如果结点s是一个函数调用表达式func(…,expr_n,…),其中:第n个参数表达式expr_n中包含一个支配指针p,省略号…表示其它参数表达式,则根据p的类型分别进行如下操作:
    操作61、如果p是符号表中已定义的一个数组,则从符号表中获取该数组的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,p,p+len,…),其中,省略号…表示原来的所有参数表达式,函数参数p表示数组的起始地址,函数参数p+len 表示数组的结束地址;
    操作62、如果p是所在函数声明的第n个形式参数,则将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    操作63、如果p是不满足以上操作61、操作62中的两种情况的指针,则从指针依赖图中获取其最终依赖指针q,如果q不存在,则认为源代码中存在指针使用前未赋初值的错误,并报错,如果q存在,则根据q的类型分别进行如下操作:
    操作631、如果q是符号表中已定义的一个数组,则从符号表中获取数组q的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,q,q+len,…),其中,省略号…表示原来的所有参数表达式,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址;
    操作632、如果q是所在函数声明的第n个形式参数,则将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    操作633、如果q是不满足以上操作631、操作632中的两种情况的指针,则认为源代码中存在指针使用前未赋初值的错误,并报错。
    进一步地,所述步骤3包括:在指针依赖图中,从p开始沿有向边往前遍历,直到访问到一个没有后继结点的指针q,那么q就是p的最终依赖指针。
    进一步地,所述步骤3包括:支配指针是指决定该表达式指向地址的主要指针变量;该表达式的其他部分决定相对于该指针指向地址的偏移量。
    进一步地,所述检测策略包括:判断要访问的地址p是否在允许的范围[begin,end)之间,如果超出该范围,则报告数组越界错误。
    进一步地,所述校正策略包括:当合法的内存范围为[begin,end),大小为n时,
    如果访问地址p为下越界,则将p和begin之间的偏移量进行模n运算,并被end减后作为映射的合法访问地址;
    如果访问地址p为上越界,则将p和end之间的偏移量进行模n运算,并加上begin作为映射的合法访问地址;
    如果访问地址p在[begin,end)范围内,则不作任何计算;
    任何的内存访问都能被映射到合法的内存范围[begin,end)内。
    进一步地,所述步骤5包括:检测策略和校正策略直接通过源代码的方式说明;或者,使用特别定义的描述语言来说明,并通过语言自动转化工具自动翻译为源代码。
    本发明提供的数组越界错误的自动检测和校正方法通过对源代码的抽象语法树进行分析,具有充分的语义信息来判断潜在的数组越界错误所在的源文件和代码行,并相应地进行源代码变换,使得在错误检测中可以使用这些位置信息,因此具有更准确的错误定位功能。进一步地,本发明通过对源代码的抽象语法树进行分析,具有充分的语义信息来判断潜在的数组越界错误的类型,并相应地进行源代码变换,减少了插入代码段的规模,简化了插入代码段的复杂程度,从而获得了更好的运行时效率和性能。进一步地,本发明通过对用户自定义检测策略和校正策略的集成和源代码变换,使得软件具有更自动化的运行时错误校正功能。
    本发明附加的方面和优点将在下面的描述中部分给出,这些将从下面的描述中变得明显,或通过本发明的实践了解到。
    附图说明
    图1示出了根据本发明的数组越界错误的自动检测和校正方法的流程示意图。
    具体实施方式
    下面详细描述本发明的实施方式,所述实施方式的示例在附图中示出,其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的,仅用于解释本发明,而不能解释为对本发明的限制。
    本技术领域技术人员可以理解的是,除非特意声明,这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。应该进一步理解的是,本发明的说 明书中使用的措辞“包括”是指存在所述特征、整数、步骤、操作、元件和/或组件,但是并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。应该理解,当我们称元件被“连接”或“耦接”到另一元件时,它可以直接连接或耦接到其他元件,或者也可以存在中间元件。此外,这里使用的“连接”或“耦接”可以包括无线连接或耦接。这里使用的措辞“和/或”包括一个或更多个相关联的列出项的任一单元和全部组合。
    本技术领域技术人员可以理解的是,除非另外定义,这里使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义?;褂Ω美斫獾氖?,诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义,并且除非像这里一样定义,不会用理想化或过于正式的含义来解释。
    下文将对上述各步骤具体展开描述。图1示出了根据本发明的数组越界错误的自动检测和校正方法的流程示意图。如图1所示,本发明的目的是通过下述技术方案实现的,具体操作步骤如下:
    步骤S11:选择待变换的源代码项目目录,或者单个源代码文件。
    步骤S12:针对待变换的源代码,利用编译器生成源代码的符号表和抽象语法树。
    步骤S13:遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算。
    其中,指针依赖图是一个有向图二元组(V,E),其中V是源代码中的指针集合(也是图的结点集合),E是源代码中的指针依赖关系集合(也是图的有向边集合)。当指针对(p,q)存在于指针依赖图中,或者存在一条从p到q的有向路径时,指针q是指针p的依赖指针,即表示指针p所指向的数组就是指针q所指向的数组。当指针q是指针p的依赖指针,并且指针q没有依赖指针时,指针q是指针p的最终依赖指针。对于指针p,可以通过如下方法获取其最终依赖指针:在指针依赖图中,从p开始沿有向边往前遍历,直到访问到一个没有后继结点的指针q时,q就是p的最终依赖指针。
    本步骤具体来说,在遍历抽象语法树的过程中,对于当前遍历到的结点s,得到其所在的源文件名filename和代码行号loc,并根据结点s的类型分别进行如下操作:
    步骤S131:如果结点s是一个带初始值的指针声明type*p=expr,其中p为指针 名,expr为表达式,且expr中包含一个支配指针q时,将(p,q)作为一条边加入指针依赖图。其中,支配指针是指决定该表达式指向地址的主要指针变量,而该表达式的其他部分决定相对于该指针指向地址的偏移量。
    步骤S132:如果结点s是一个指针赋值表达式p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q时,将(p,q)作为一条边加入指针依赖图。
    步骤S133:如果结点s是一个数组下标表达式p[expr],其中p为指针名或数组名,expr为表达式时,根据p的类型分别进行如下操作:
    步骤S1331:当p是符号表中已定义的一个数组时,从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,p,p+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S1332:当p是所在函数声明的第n个形式参数时,从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S1333:当p是不满足以上步骤S1331、步骤S1332中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S13331:当q是符号表中已定义的一个数组时,从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,q,q+len,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S13332:当q是所在函数声明的第n个形式参数时,从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数p+expr表示数组下标表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S13333:当q是不满足以上步骤S13331、步骤S13332中的两种情况的指针时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S134:如果结点s是一个指针访问表达式*expr,其中expr为表达式,且expr中包含一个支配指针p时,根据p的类型分别进行如下操作:
    步骤S1341:当p是符号表中已定义的一个数组时,从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,p,p+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S1342:当p是所在函数声明的第n个形式参数时,从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S1343:当p是不满足以上步骤S1341、步骤S1342中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S13431:当q是符号表中已定义的一个数组时,从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,q,q+len,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S13432:当q是所在函数声明的第n个形式参数时,从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    其中,函数参数expr表示指针访问表达式访问的内存地址,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址,函数参数filename表示源文件名,函数参数loc表示代码行号;
    步骤S13433:当q是不满足以上步骤S13431、步骤S13432中的两种情况的指针时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S135:如果结点s是一个函数声明或函数定义表达式type func(…,type_n expr_n,…),其中:第n个参数表达式expr_n为type_n类型的数组或指针声明p,省略号…表示其它参数表达式时,将该函数声明或函数定义替换为如下函数:
    type func(…,type_n expr_n,void*__MNT_CHK_AAV_B_n,void*__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个参数表达式的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个参数表达式的结束地址;
    步骤S136:如果结点s是一个函数调用表达式func(…,expr_n,…),其中:第n个参数表达式expr_n中包含一个支配指针p,省略号…表示其它参数表达式时,根据p的类型分别进行如下操作:
    步骤S1361:当p是符号表中已定义的一个数组时,从符号表中获取该数组的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,p,p+len,…),其中,省略号…表示原来的所有参数表达式,函数参数p表示数组的起始地址,函数参数p+len表示数组的结束地址;
    步骤S1362:当p是所在函数声明的第n个形式参数时,将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    步骤S1363:当p是不满足以上步骤S1361、步骤S1362中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S13631:当q是符号表中已定义的一个数组时,从符号表中获取数组q的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,q,q+len,…),其中,省略号…表示原来的所有参数表达式,函数参数q表示数组的起始地址,函数参数q+len表示数组的结束地址;
    步骤S13632:当q是所在函数声明的第n个形式参数时,将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    其中,省略号…表示原来的所有参数表达式,函数参数__MNT_CHK_AAV_B_n表示第n个形式参数的起始地址,函数参数__MNT_CHK_AAV_E_n表示第n个形式参数的结束地址;
    步骤S13633:当q是不满足以上步骤S13631、步骤S13632中的两种情况的指针时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S14:根据步骤S13的计算结果,在源代码中将需替换的部分源代码进行替换,生成变换后的源代码,并保存到新项目目录或新文件。
    步骤S15:定义数组越界检测策略和校正策略,并将这些策略转化为函数__MNT_CHK_AAV的定义。其中,检测策略是指:如何判断对数组的访问是否超出数组的内存范围。例如,一种可行的检测策略为:判断要访问的地址p是否在允许的范围[begin,end)之间,当超出该范围时,报告数组越界错误。该策略可以被转化为如下源代码:


    校正策略是指:如何将超出数组的内存范围的数组访问映射到合法的内存范围以内。例如,一种可行的校正策略为求模运算:假设合法的内存范围为[begin,end),大小为n,(1)当访问地址p为下越界时,将p和begin之间的偏移量进行模n运算,并被end减后作为映射的合法访问地址;(2)当访问地址p为上越界时,将p和end之间的偏移量进行模n运算,并加上begin作为映射的合法访问地址;(3)当访问地址p在[begin,end)范围内时,不作任何计算。这样,任何的内存访问都可以被映射到合法的内存范围[begin,end)内。该策略可以被转化为如下源代码:

    检测策略和校正策略可以直接通过源代码的方式说明,也可以使用特别定义的描述语言来说明,然后通过语言自动转化工具自动翻译为源代码。最后将按照策略生成的函数__MNT_CHK_AAV的定义写入变换后源代码的开头部分。
    步骤S16:将变换后的项目目录或文件用原编译器进行编译,生成目标系统上的可执行文件。
    步骤S17:把生成的可执行文件部署到目标系统并运行,当可执行文件运行到那些替换或插入的代码段时,将自动检测和校正数组越界错误,并准确报告错误对应的源代码位置。
    经过上述步骤的操作,即可准确地在软件运行过程中检测出数组越界错误,并进行自动校正。
    有益效果:本发明提出的方法与已有技术相比较,有如下优点:
    (1)本发明通过对源代码的抽象语法树进行分析,具有充分的语义信息来判断潜在的数组越界错误所在的源文件和代码行,并相应地进行源代码变换,使得在错误检测中可以使用这些位置信息,因此具有更准确的错误定位功能。
    (2)本发明通过对源代码的抽象语法树进行分析,具有充分的语义信息来判断潜在的数组越界错误的类型,并相应地进行源代码变换,减少了插入代码段的规模,简化了插入代码段的复杂程度,从而获得了更好的运行时效率和性能。
    (3)本发明通过对用户自定义检测策略和校正策略的集成和源代码变换,使得软件具有更自动化的运行时错误校正功能。
    本发明可以解决安全关键嵌入式工业控制软件和应用软件系统的数组越界错误检测和校正中的难题,对于准确定位和校正错误,在软件研发和维护阶段提高软件产品的质量有非常重要的作用,有良好的社会效益。
    下文将以本发明方法对一段C语言源代码进行检测和校正为例,进一步具体说明本发明的有关方法、流程及相关步骤。例如,源代码如下(文件名为array.c):


    本发明方法的具体操作步骤如下:
    步骤S21:选择待变换的源代码项目目录,或者单个源代码文件。
    本实施例中,选择文件array.c。
    步骤S22:针对待变换的源代码,利用编译器生成源代码的符号表和抽象语法树。
    本实施例中,所述待变换的源代码为C/C++源代码。
    步骤S23:遍历抽象语法树中的所有结点,构造指针依赖图,并进行源代码变换计算。
    其中,指针依赖图是一个有向图二元组(V,E),其中V是源代码中的指针集合(也是图的结点集合),E是源代码中的指针依赖关系集合(也是图的有向边集合)。当指针对(p,q)存在于指针依赖图中,或者存在一条从p到q的有向路径时,指针q是指针p的依赖指针,即表示指针p所指向的数组就是指针q所指向的数组。当指针q是指针p的依赖指针,并且指针q没有依赖指针时,指针q是指针p的最终依赖指针。对于指针p,可以通过如下方法获取其最终依赖指针:在指针依赖图中,从p开始沿有向边往前遍历,直到访问到一个没有后继结点的指针q时,q就是p的最终依赖指针。
    本步骤具体来说,在遍历抽象语法树的过程中,对于当前遍历到的结点s,得到其所在的源文件名filename和代码行号loc,并根据结点s的类型分别进行如下操作:
    步骤S231:如果结点s是一个带初始值的指针声明type*p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q时,将(p,q)作为一条边加入指针依赖图。其中,支配指针是指决定该表达式指向地址的主要指针变量,而该表达式的其他部分决定相对于该指针指向地址的偏移量。
    本实施例中,由于main函数中的指针声明“int*pa=a+2”,其中a为支配指针, 因此将(main.pa,main.a)加入指针依赖图。
    步骤S232:如果结点s是一个指针赋值表达式p=expr,其中p为指针名,expr为表达式,且expr中包含一个支配指针q时,将(p,q)作为一条边加入指针依赖图。
    本实施例中,由于foo函数中的指针赋值表达式“pp=p+1”,其中p为支配指针,因此将(foo.pp,foo.p)加入指针依赖图。
    步骤S233:如果结点s是一个数组下标表达式p[expr],其中p为指针名或数组名,expr为表达式时,根据p的类型分别进行如下操作:
    步骤S2331:当p是符号表中已定义的一个数组时,从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,p,p+len,filename,loc)))
    本实施例中,main函数中的表达式“a[i]”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(a+i,a,a+10,"array.c",12)))
    本实施例中,main函数中的表达式“a[i*2-2]”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(a+(i*2-2),a,a+10,"array.c",15)))
    步骤S2332:当p是所在函数声明的第n个形式参数时,从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    本实施例中,foo函数中的表达式“p[i*2-2]”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(p+(i*2-2),__MNT_CHK_AAV_B_1,__MNT_CHK_AAV_E_1,"array.c",4)))
    步骤S2333:当p是不满足以上步骤S2331、步骤S2332中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S23331:当q是符号表中已定义的一个数组时,从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(p+expr,q,q+len,filename,loc)))
    步骤S23332:当q是所在函数声明的第n个形式参数时,从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(p+expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    步骤S23333:当q是不满足以上步骤S23331、步骤S23332中的两种情况的指针 时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S234:如果结点s是一个指针访问表达式*expr,其中expr为表达式,且expr中包含一个支配指针p时,根据p的类型分别进行如下操作:
    步骤S2341:当p是符号表中已定义的一个数组时,从符号表中获取该数组的类型type和长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,p,p+len,filename,loc)))
    本实施例中,main函数中的表达式“*(a+i)”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(a+i,a,a+10,"array.c",16)))
    步骤S2342:当p是所在函数声明的第n个形式参数时,从符号表中获取该指针的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    本实施例中,foo函数中的表达式“*(p+i*2-1)”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(p+i*2-1,__MNT_CHK_AAV_B_1,__MNT_CHK_AAV_E_1,"array.c",5)))
    步骤S2343:当p是不满足以上步骤S2341、步骤S2342中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S23431:当q是符号表中已定义的一个数组时,从符号表中获取指针p的类型type和数组q的长度len,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHECK_AAV(expr,q,q+len,filename,loc)))
    本实施例中,由于(main.pa,main.a)在指针依赖图中,main函数中的表达式“*(pa+i-1)”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(pa+i-1,a,a+10,"array.c",17)))
    步骤S23432:当q是所在函数声明的第n个形式参数时,从符号表中获取指针p的类型type,然后将该表达式替换为如下函数调用:
    *((type*)(__MNT_CHK_AAV(expr,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,filename,loc)))
    本实施例中,由于(foo.pp,foo.p)在指针依赖图中,foo函数中的表达式“*(pp+i+1)”被替换为如下函数调用:
    *((int*)(__MNT_CHK_AAV(pp+i+1,__MNT_CHK_AAV_B_1,__MNT_CHK_AAV_E_1,"array.c",6)))
    步骤S23433:当q是不满足以上步骤S23431、步骤S23432中的两种情况的指针 时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S235:如果结点s是一个函数声明或函数定义表达式type func(…,type_n expr_n,…),其中:第n个参数表达式expr_n为type_n类型的数组或指针声明p时,将该函数声明或函数定义替换为如下函数:
    type func(…,type_n expr_n,void*__MNT_CHK_AAV_B_n,void*__MNT_CHK_AAV_E_n,…)
    本实施例中,foo函数的定义“void foo(int*p)”被替换为如下函数定义:
    void foo(int*p,void*__MNT_CHK_AAV_B_1,void*__MNT_CHK_AAV_E_1)
    步骤S236:如果结点s是一个函数调用表达式func(…,expr_n,…),其中:第n个参数表达式expr_n中包含一个支配指针p时,根据p的类型分别进行如下操作:
    步骤S2361:当p是符号表中已定义的一个数组时,从符号表中获取该数组的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,p,p+len,…)。
    本实施例中,main函数中的表达式“foo(a+1)”被替换为如下函数调用:foo(a+1,a,a+10)。
    步骤S2362:当p是所在函数声明的第n个形式参数时,将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    步骤S2363:当p是不满足以上步骤S2361、步骤S2362中的两种情况的指针时,从指针依赖图中获取其最终依赖指针q。当q不存在时,认为源代码中存在指针使用前未赋初值的错误,并报错。当q存在时,根据q的类型分别进行如下操作:
    步骤S23631:当q是符号表中已定义的一个数组时,从符号表中获取数组q的长度len,然后将该表达式替换为如下函数调用:func(…,expr_n,q,q+len,…)。
    本实施例中,由于(main.pa,main.a)在指针依赖图中,main函数中的表达式“foo(pa+2)”被替换为如下函数调用:foo(pa+2,a,a+10)。
    步骤S23632:当q是所在函数声明的第n个形式参数时,将该表达式替换为如下函数调用:
    func(…,expr_n,__MNT_CHK_AAV_B_n,__MNT_CHK_AAV_E_n,…)
    步骤S23633:当q是不满足以上步骤S23631、步骤S23632中的两种情况的指针时,认为源代码中存在指针使用前未赋初值的错误,并报错。
    步骤S24:根据步骤S23的计算结果,在源代码中将需替换的部分源代码进行替 换,生成变换后的源代码,并保存到新项目目录或新文件。
    本实施例中,进行源代码变换后生成的源代码(文件名array_out.c)如下:

    步骤S25:定义数组越界检测策略和校正策略,并将这些策略转化为函数__MNT_CHK_AAV的定义。其中,检测策略是指:如何判断对数组的访问是否超出数组的内存范围。一种可行的检测策略为:判断要访问的地址p是否在允许的范围[begin,end)之间,当超出该范围时,报告数组越界错误。该策略可以被转化为如下源代码:


    校正策略是指:如何将超出数组的内存范围的数组访问映射到合法的内存范围以内。一种可行的校正策略为求模运算:假设合法的内存范围为[begin,end),大小为n,(1)当访问地址p为下越界时,将p和begin之间的偏移量进行模n运算,并被end减后作为映射的合法访问地址;(2)当访问地址p为上越界时,将p和end之间的偏移量进行模n运算,并加上begin作为映射的合法访问地址;(3)当访问地址p在[begin,end)范围内时,不作任何计算。这样,任何的内存访问都可以被映射到合法的内存范围[begin,end)内。该策略可以被转化为如下源代码:

    检测策略和校正策略可以直接通过源代码的方式说明,也可以使用特别定义的描述语言来说明,然后通过语言自动转化工具自动翻译为源代码。最后将按照策略生成的函数__MNT_CHK_AAV的定义写入变换后源代码的开头部分。
    本实施例中,将以下函数写入array_out.c的开头部分:


    步骤S26:将变换后的项目目录或文件用原编译器进行编译,生成目标系统上的可执行文件。
    本实施例中,编译文件array_out.c。
    步骤S27:把生成的可执行文件部署到目标系统并运行,当可执行文件运行到那些替换或插入的代码段时,将自动检测和校正数组越界错误,并准确报告错误对应的源代码位置。
    本实施例中,由于检测策略和校正策略的使用,array.c源代码中第11-12行循环语句中的数组越界错误将在软件运行过程中被完全正确校正,并正确地得到数组所有元素的总和,并且准确报告源代码中第12行引起的数组越界错误。
    通过上述实施例发现,通过源代码变换方法,将所有对数组的访问都替换为了函数调用,并在该函数中对数组越界错误进行自动检测和校正。因此,本发明能够准确地在软件运行过程中对数组越界错误进行自动检测和校正。
    本发明可以解决安全关键嵌入式工业控制软件和应用软件系统的数组越界错误检测和校正中的难题,对于准确定位和校正错误,在软件研发和维护阶段提高软件产品的质量有非常重要的作用,有良好的社会效益。
    本技术领域技术人员可以理解的是,本发明可以涉及用于执行本申请中所述操作中的一项或多项操作的设备。所述设备可以为所需的目的而专门设计和制造,或者也可以包括通用计算机中的已知设备,所述通用计算机有存储在其内的程序选择性地激活或重构。这样的计算机程序可以被存储在设备(例如,计算机)可读介质中或者存储在适于存储电子指令并分别耦联到总线的任何类型的介质中,所述计算机可读介质 包括但不限于任何类型的盘(包括软盘、硬盘、光盘、CD-ROM、和磁光盘)、随机存储器(RAM)、只读存储器(ROM)、电可编程ROM、电可擦ROM(EPROM)、电可擦除可编程ROM(EEPROM)、闪存、磁性卡片或光线卡片??啥两橹拾ㄓ糜谝杂缮璞福ɡ?,计算机)可读的形式存储或传输信息的任何机构。例如,可读介质包括随机存储器(RAM)、只读存储器(ROM)、磁盘存储介质、光学存储介质、闪存装置、以电的、光的、声的或其他的形式传播的信号(例如载波、红外信号、数字信号)等。
    本技术领域技术人员可以理解的是,可以用计算机程序指令来实现这些结构图和/或框图和/或流图中的每个框以及这些结构图和/或框图和/或流图中的框的组合??梢越庑┘扑慊绦蛑噶钐峁└ㄓ眉扑慊?、专业计算机或其他可编程数据处理方法的处理器来生成机器,从而通过计算机或其他可编程数据处理方法的处理器来执行的指令创建了用于实现结构图和/或框图和/或流图的框或多个框中指定的方法。
    本技术领域技术人员可以理解的是,本发明中已经讨论过的各种操作、方法、流程中的步骤、措施、方案可以被交替、更改、组合或删除。进一步地,具有本发明中已经讨论过的各种操作、方法、流程中的其他步骤、措施、方案也可以被交替、更改、重排、分解、组合或删除。进一步地,现有技术中的具有与本发明中公开的各种操作、方法、流程中的步骤、措施、方案也可以被交替、更改、重排、分解、组合或删除。
    以上所述仅是本发明的部分实施方式,应当指出,对于本技术领域的普通技术人员来说,在不脱离本发明原理的前提下,还可以做出若干改进和润饰,这些改进和润饰也应视为本发明的?;し段?。

    关于本文
    本文标题:数组越界错误的自动检测和校正方法.pdf
    链接地址://www.4mum.com.cn/p-6185327.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
  • 000001上证指数新浪行情 大额股票配资 股票融资费用和利息 如何炒股票新手入门 2013年上证指数数据 上证指数腾讯 股票涨跌原因分析 好股票推荐 上证指数金融界行情中心 中长期股票推荐 黑马股票推荐2017 今日股票行情大盘走势 股票怎么玩 股票推荐1只暴涨股 不要碰炒股男人 世界主要股票指数