程序设计是计算机、软件工程等工科专业的第一门核心必修专业课程, 其教学内容通常包括C程序设计语言^[1]、面向对象程序设计语言(例如C++)^[2]. 由于后续专业课程(例如数据结构、编译原理、软件工程、软件测试等)都需要使用程序设计来完成实验和课程设计, 而且程序设计也是计算机和软件行业招聘面试的核心考查内容, 所以熟练地掌握程序设计技能不仅是学习后续专业课程的基础, 也是获得理想工作机会的重要条件. 因此, 如何改进程序设计课程教学、让学生更好地掌握课程知识点是重要的研究课题^[3-7].

笔者在教学实践中发现, 虽然采用了网络教学组织^{[3, 4]}和在线判题^[5-7]教学系统, 学生还是很难掌握程序设计语言中一些复杂的或抽象的理论知识, 也很难将这些知识正确地运用到编程实践中. 以C程序设计教学为例, 指针和内存操作较为复杂^[1]. 程序内存被划分为代码段、数据段、BSS段、栈、堆等不同的段, 而每个段都有不同的访问规则^[8], 例如: 代码段中的数据只能读不能写, 栈中的数据不能被显式释放, 堆中分配的内存块被释放后不能再次访问, 对内存块的访问不能超过该内存块的上界和下界等. 所以照本宣科式地讲授相关的理论知识, 学生难以消化吸收, 更无法正确运用, 使得编写的程序经常带有内存错误, 导致错误的运行结果和耗时的调试过程. 事实上, 在工业界的软件开发实践中, 内存错误也一直是最常见、危害最大的程序错误之一, 它可以导致数据腐败、安全漏洞和程序崩溃等致命后果, 例如阿丽亚娜5号火箭控制系统软件的内存溢出错误导致火箭在升空后爆炸^[9]. 因此, 教师有必要使用教学系统帮助学生牢固掌握指针和内存操作的相关知识、更快地找到程序中的内存错误, 从而正确运用指针和内存操作.

以面向对象程序设计教学为例, 封装、继承、多态是面向对象的三大特性^[2], 但是这些概念较为抽象. 注意, C程序设计教学关注的是程序具体功能相关的知识点, 如循环语句、函数等. 与之不同, 面向对象程序设计教学关注的是非功能的知识点, 例如封装、继承、多态的主要目标是改善大规模代码的模块化、可维护性、可复用性、健壮性等. 所以咬文嚼字式地讲授相关的概念定义, 或者通过小例子辅助教学, 学生都难以理解这些特性的优点, 更无法主动地在编程实践中合理地运用, 使得编写的程序经常不具备面向对象的特征, 导致程序模块性差、难于维护. 因此, 教师有必要使用教学系统帮助学生深入理解面向对象的特性, 从而正确运用面向对象程序设计思想.

基于上述教学需求, 本文设计并使用C++程序设计语言实现了面向程序设计课程的教学系统: C程序内存安全性动态分析系统(以下称为Movec). 该系统包含了C程序编译器前端, 通过递归式遍历和重写程序源代码的抽象语法树(AST), 实现对程序源代码的自动插桩; 通过编译运行插桩后的源代码, 实现对内存错误的动态检测. 该系统综合运用了C程序设计、面向对象程序设计(C++)、数据结构、编译原理、软件工程、软件测试等计算机和软件工程专业核心课程的知识, 同时可以展现这些知识之间的深度融合. 学生通过学习和使用该系统有助于理解和掌握相关的理论知识, 以及这些理论知识在实际软件开发过程中的应用, 可以激发学生学习的主动性和钻研的兴趣, 从而有效地提高教学效果.

1 总体规划 1.1 基本技术

程序分析技术是一种对程序行为进行自动分析的过程, 通常用于发现程序中的缺陷和错误, 例如内存安全性缺陷、死循环等逻辑错误.

程序分析技术分为静态和动态两种. 静态分析不需要运行程序, 而是通过对程序代码进行逻辑推理来检测错误. 由于静态分析需要确保性能(在短时间内报告结果), 而这是以检测精度为代价的, 因此通常有误报和漏报. 动态分析通过代码插桩技术在代码中插入用于错误检测的代码片段, 从而在运行时实现对程序执行过程的分析和错误检测^[10]. 动态分析的优点是考虑了程序实际运行环境等因素, 理论上不存在误报. 因此本系统采用基于动态分析的方法.

动态分析所采用的代码插桩技术通常对程序的中间表示^[11]或二进制代码插桩^[12], 导致无法报告错误在源代码中的准确位置, 给错误调试带来障碍. 因此本系统采用源代码插桩技术^[13], 即直接对源代码进行重写, 在检测到错误时, 可以报告错误所在的源文件名和行号等.

1.2 系统结构

图1展示了Movec系统的总体结构, 主要由C程序解析器和递归式AST访问者组成. 对于用户给定的C程序, Movec首先使用C程序解析器将程序源代码解析为AST, 然后通过递归式遍历和访问AST上的每个节点, 分析程序语义, 并插入相应的用于错误检测的代码片段, 生成插桩后的源代码和接口文件(包括实现错误检测算法的数据结构和接口函数). 用户通过编译插桩后的源代码, 得到插桩后的可执行程序. 最后用户运行该程序, 实现对内存错误的动态检测.

2 错误检测与自动插桩算法

内存错误动态检测的基本思想是为每个指针变量分配一个指针元数据(Pointer Meta Data, PMD), 用于记录指针变量所指向的内存块的下界、上界和状态信息, 并在程序通过指针变量访问内存时检测指针元数据所记录的信息是否允许这次访问. 下面我们通过实例介绍错误检测算法的基本思想.

实例1. 下列C程序首先将指针p初始化为指向变量i, 然后对指针p+5进行解引用和赋值. 显然, 由于p+5超出了变量i所在内存块的范围, 因此会发生内存溢出错误.

int i=1, *p=&i;

*(p+5)=1;

我们的检测算法可以发现该错误. 在程序初始化指针p之后, 检测算法首先为指针p分配一个指针元数据(如图2所示), 用于记录p所指向的内存块的下界&i、上界&i+1和状态stack, 其中stack表示该内存块(变量i)是被存储在栈中的有效变量(即没有被释放), 然后将该指针元数据插入指针元数据表, 并使用p的地址&p作为该元数据的索引值, 用于加快查找指针元数据的速度.

在程序对指针p+5进行解引用访问之前, 检测算法首先使用p的地址&p作为索引值在指针元数据表中查找p的指针元数据, 然后检测程序即将访问的内存块范围是否在指针元数据所记录的下界和上界之间. 由于程序即将访问的内存块范围是从&i+5到&i+6, 超出了元数据所记录的从&i到&i+1的范围, 因此存在内存溢出错误. 此时检测算法将报告内存错误及其所在的源文件名、行号、列号和导致错误的内存访问表达式“*(p+5)”.

实例2. 下列C程序首先在函数foo中将指针n初始化为指向函数foo中的局部变量x, 然后在退出函数foo后对指针n进行解引用和赋值. 显然, 由于n所指向的变量x此时是无效变量(即已经被释放), 因此会发生内存释放后访问的错误.

void foo(int **pa)　　　void main() {

{　　　　　　　　　　　　int *n;

　int x;　　　　　　　　　foo(&n);

　*pa=&x;　　　　　　　　*n=1;

}　　　　　　　　　　　}

我们的检测算法可以发现该错误. 在程序初始化指针n之后, 检测算法首先为指针n分配一个指针元数据(如图3(a)所示), 用于记录n所指向的内存块的下界&x、上界&x+1和状态stack, 然后将该指针元数据插入指针元数据表, 并使用n的地址&n作为该元数据的索引值.

在程序退出函数foo之前, 程序释放函数foo中所有的局部变量, 检测算法将n的指针元数据中的状态改为invalid, 表示n所指向的内存块(变量x)已经被释放(如图3(b)所示).

在程序对指针n进行解引用访问之前, 检测算法首先使用n的地址&n作为索引值在指针元数据表中查找n的指针元数据, 然后检测指针元数据所记录的状态是否不是invalid. 由于此时元数据所记录的状态是invalid, 因此存在内存释放后访问的错误. 此时检测算法将报告内存错误及其所在的源文件名、行号、列号和导致错误的内存访问表达式“*n”.

我们通过以下3个接口函数来实现以上错误检测算法的主要功能:

1) 接口函数pmd_tbl_update_as用于更新给定指针变量p的指针元数据, 将&p所索引的指针元数据的内容设置为给定的下界、上界和状态信息.

2) 接口函数pmd_tbl_lookup用于获取给定指针变量p的指针元数据, 返回&p所索引的指针元数据的地址.

3) 接口函数check_dpv用于检测要访问的内存块范围是否在指针元数据所记录的下界和上界之间、状态是否有效.

接下来我们需要实现对程序源代码的自动插桩, 使得程序能在运行时调用以上接口实现对内存错误的动态检测. 算法1给出了自动插桩的基本思想: 通过递归式遍历和访问程序源代码AST上的每个节点, 在合适的位置插入对以上接口的调用. 例如, 在指针变量定义之后插入对其pmd的初始化操作, 在指针变量赋值语句之后插入对其pmd的更新操作, 在指针解引用表达式之前插入对比其pmd和实际访问的内存块范围的检测操作.

算法1. 内存错误动态检测的自动插桩算法

遍历程序源代码AST, 对于每个访问到的节点:

1)　如果该节点是指针变量定义, 例如“T *p;”或带有空初始值“T *p=NULL;”, 则在该语句后插入接口调用:

　　pmd_tbl_update_as(&p, NULL, NULL, NULL);

2)　如果该节点是从指针常量到指针变量的赋值语句, 例如“p=&i;”, 则在该语句后插入接口调用:

　　pmd_tbl_update_as(&p, &i, &i+1, i_status);

3)　如果该节点是从指针变量到指针变量的赋值语句, 例如“p1=p;”, “p1=p+I; ”或“p1=&p[i];”, 则在该语句后插入接口调用:

　　pmd=pmd_tbl_lookup(&p);

　　pmd_tbl_update_as(&p1, pmd->base, pmd->bound, pmd->status);

4)　如果该节点包含指针解引用表达式, 例如“i=*p1”或“*p1=i”, 则在该语句前插入接口调用:

　　check_dpv(pmd_tbl_lookup(&p1), p1, sizeof(*p1));

然后递归访问该节点的子节点.

3 系统开发

Movec系统的开发包括两部分: 使用C程序设计语言实现错误检测算法, 使用C++程序设计语言实现源代码自动插桩算法. 为了用户可以在不同的平台上使用Movec, 我们充分利用C/C++的跨平台特性, 采用基于CMake编译系统的跨平台架构, 使得Movec可以在Linux和Windows上运行.

3.1 错误检测函数库的实现

由于C程序设计语言并不自带容器类数据结构, 因此我们从零开始实现了一个高效的指针元数据表. 如图4所示, 指针变量ptr的指针元数据包括该指针变量的地址&ptr、所指向内存块的下界base、上界bound和状态信息节点的地址&st. 由于多个指针(例如ptr1和ptr2)可能指向同一个内存块, 因此内存块的状态信息节点必须是一个独立的节点, 这样才可能被多个指针元数据引用. 整个指针元数据表是使用指针变量地址为索引值的哈希表.图5展示了指针元数据结构定义的UML图, 其中指针变量的地址是指向指针的指针类型, 下界和上界是指针类型, 状态信息节点的地址是指向状态信息节点的指针类型. 在状态信息节点中, 我们使用无符号整数表示内存块的当前状态, 例如invalid、stack、heap等.

基于指针元数据表, 实现错误检测算法的3个接口函数是较为直接的. 例如, 接口函数pmd_tbl_update_as先在指针元数据表中查找给定指针变量p的指针元数据, 如果未找到则插入一个新的指针元数据, 然后对该元数据中的成员变量进行赋值.

3.2 源代码自动插桩的实现

自动插桩实现的关键在于递归式AST访问者的实现. 为了展示面向对象程序设计的特性, 在实现中融合了封装、继承和多态. 首先, 设计了一个基本的AST访问者类ASTVisitorBase, 包含对程序源代码AST上各种节点进行访问的成员虚函数VisitX, 然后实现了Traverse成员函数, 在对AST进行递归式遍历的同时调用VisitX函数来对AST上的每个节点进行访问, 其中X可以是任意类型的节点, 例如访问声明Decl的函数VisitDecl和访问语句Stmt的函数VisitStmt等. 然后, 设计了一个实现插桩的AST访问者类ASTVisitor, 继承于ASTVisitorBase, 并对其中的成员虚函数VisitX进行虚函数重载, 实现源代码插桩功能.

4 实施方案

Movec的使用非常简便. 用户只需要执行3个命令即可得到检测结果: 运行Movec对源代码进行自动插桩; 运行编译器将插桩后的源代码编译为可执行程序; 运行插桩后的可执行程序得到检测结果. 例如, 图6和图7分别展示了对第2节中的实例1和实例2进行检测的过程. 结果显示, 实例1中对指针p+5的解引用导致了空间错误(即内存溢出错误), 实例2中对指针n的解引用导致了时间错误(即内存释放后访问). 值得注意的是, 检测结果也报告了错误在源代码中的精确位置, 包括源文件名和行号等.

Movec可以被用于C程序设计语言的教学, 有效提高教学效果. 首先, 学生可以对自己编写的程序运行Movec, 更快地找到程序中的内存错误, 极大地缩短调试时间, 提高学习效率. 通过长期使用Movec, 学生能养成正确运用指针和内存操作的习惯, 提高编程能力. 第二, Movec的错误检测函数库可以作为C语言的演示系统, 帮助学生掌握C语言中一些复杂的理论知识. 函数库的实现不仅大量使用了基本的条件语句、循环语句、数组、函数等, 还覆盖了较为复杂的指针和内存操作、结构体和链表等知识. 例如, 指针元数据采用结构体实现, 并包含了指向状态信息节点的指针; 指针元数据表采用基于动态内存分配的哈希表实现, 并采用链表来处理哈希冲突. 这可以帮助学生深入理解这些理论知识, 并掌握如何将这些知识正确地运用到编程实践中.

Movec可以被用于面向对象程序设计语言(C++)的教学, 有效提高教学效果. Movec的源代码自动插桩模块可以作为C++语言的演示系统, 帮助学生掌握C++语言中一些抽象的理论知识. 插桩模块的实现覆盖了重要但抽象的封装、继承和多态等知识. 例如, AST中所有的语法节点类型都采用了封装的类来实现, 并且采用继承来描述相关节点类型之间的联系; 递归式AST访问者的实现也采用了封装、继承和多态, 即继承于一个基本的AST访问者类, 并对其中的AST节点访问函数进行虚函数重载; 通过这些设计改善了大规模代码的模块化、可维护性、可复用性和健壮性. 这可以帮助学生深入理解这些面向对象特性的优点, 并主动地将这些知识合理地运用到编程实践中.

Movec也可以作为数据结构、编译原理、软件工程、软件测试等课程的案例分析材料, 全面贯穿计算机、软件工程等专业的培养计划.

5 结论

程序设计是计算机、软件工程等工科专业的第一门核心必修专业课程. 熟练地掌握程序设计技能不仅是学习后续专业课程的基础, 也是获得理想工作机会的重要条件. 笔者在教学实践中发现, 已有的教学系统只支持网络教学组织^{[3, 4]}和在线判题^[5-7], 并不能帮助学生掌握课程难点. 为此, 我们设计和实现了面向程序设计课程的教学系统: C程序内存安全性动态分析系统. 该系统综合运用了C程序设计、面向对象程序设计(C++)、数据结构、编译原理、软件工程、软件测试等计算机和软件工程专业核心课程的知识, 同时可以展现这些知识之间的深度融合. 从教学效果来看, 该系统不仅可以帮助学生理解和掌握相关的理论知识, 以及这些理论知识在实际软件开发过程中的应用, 还可以激发学生学习的主动性和钻研的兴趣, 从而有效地提高教学效果.