程序设计是计算机专业的第一门核心必修专业课程, 但是在教学实践中, 学生很难掌握程序设计语言中一些复杂的或抽象的理论知识. 为了提高教学效果, 针对程序设计课程教学的难点, 本文设计和实现了面向程序设计课程的教学系统: 程序动态分析系统. 该系统通过综合运用程序设计等专业课程的知识, 实现了程序错误检测和源代码自动插桩, 同时可以展现这些知识之间的深度融合. 我们将该系统应用于程序设计教学实践, 有助于学生理解和掌握程序设计课程的难点, 以及这些知识在实际软件开发过程中的应用, 从而有效提高教学效果.
The course of programming languages is usually the first core course for the majority of computer science. However, in the teaching practice, it is hard for students to master some complex and abstract knowledge in programming languages. To overcome the difficulties in teaching the course of programming languages, in this study, we design and implement a teaching system for the course of programming languages—a program dynamic analysis system. This system, by applying the knowledge of programming languages and some other core professional courses, implements program error detection and automated source instrumentation. We apply this system to the teaching practice, which helps students to understand and master the complex and abstract concepts in the course of programming languages, and their applications in real-world software development, thus to improve the teaching effectiveness.
程序设计是计算机、软件工程等工科专业的第一门核心必修专业课程, 其教学内容通常包括C程序设计语言[
笔者在教学实践中发现, 虽然采用了网络教学组织[
以面向对象程序设计教学为例, 封装、继承、多态是面向对象的三大特性[
基于上述教学需求, 本文设计并使用C++程序设计语言实现了面向程序设计课程的教学系统: C程序内存安全性动态分析系统(以下称为Movec). 该系统包含了C程序编译器前端, 通过递归式遍历和重写程序源代码的抽象语法树(AST), 实现对程序源代码的自动插桩; 通过编译运行插桩后的源代码, 实现对内存错误的动态检测. 该系统综合运用了C程序设计、面向对象程序设计(C++)、数据结构、编译原理、软件工程、软件测试等计算机和软件工程专业核心课程的知识, 同时可以展现这些知识之间的深度融合. 学生通过学习和使用该系统有助于理解和掌握相关的理论知识, 以及这些理论知识在实际软件开发过程中的应用, 可以激发学生学习的主动性和钻研的兴趣, 从而有效地提高教学效果.
程序分析技术是一种对程序行为进行自动分析的过程, 通常用于发现程序中的缺陷和错误, 例如内存安全性缺陷、死循环等逻辑错误.
程序分析技术分为静态和动态两种. 静态分析不需要运行程序, 而是通过对程序代码进行逻辑推理来检测错误. 由于静态分析需要确保性能(在短时间内报告结果), 而这是以检测精度为代价的, 因此通常有误报和漏报. 动态分析通过代码插桩技术在代码中插入用于错误检测的代码片段, 从而在运行时实现对程序执行过程的分析和错误检测[
动态分析所采用的代码插桩技术通常对程序的中间表示[
内存错误动态检测的基本思想是为每个指针变量分配一个指针元数据(Pointer Meta Data, PMD), 用于记录指针变量所指向的内存块的下界、上界和状态信息, 并在程序通过指针变量访问内存时检测指针元数据所记录的信息是否允许这次访问. 下面我们通过实例介绍错误检测算法的基本思想.
系统结构图
实例1. 下列C程序首先将指针p初始化为指向变量i, 然后对指针p+5进行解引用和赋值. 显然, 由于p+5超出了变量i所在内存块的范围, 因此会发生内存溢出错误.
int i=1, *p=&i;
*(p+5)=1;
我们的检测算法可以发现该错误. 在程序初始化指针p之后, 检测算法首先为指针p分配一个指针元数据(如
实例1中指针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分配一个指针元数据(如
实例2中指针n的指针元数据及其变化
在程序退出函数foo之前, 程序释放函数foo中所有的局部变量, 检测算法将n的指针元数据中的状态改为invalid, 表示n所指向的内存块(变量x)已经被释放(如
在程序对指针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));
然后递归访问该节点的子节点.
Movec系统的开发包括两部分: 使用C程序设计语言实现错误检测算法, 使用C++程序设计语言实现源代码自动插桩算法. 为了用户可以在不同的平台上使用Movec, 我们充分利用C/C++的跨平台特性, 采用基于CMake编译系统的跨平台架构, 使得Movec可以在Linux和Windows上运行.
由于C程序设计语言并不自带容器类数据结构, 因此我们从零开始实现了一个高效的指针元数据表. 如
指针元数据表
指针元数据
基于指针元数据表, 实现错误检测算法的3个接口函数是较为直接的. 例如, 接口函数pmd_tbl_update_as先在指针元数据表中查找给定指针变量p的指针元数据, 如果未找到则插入一个新的指针元数据, 然后对该元数据中的成员变量进行赋值.
自动插桩实现的关键在于递归式AST访问者的实现. 为了展示面向对象程序设计的特性, 在实现中融合了封装、继承和多态. 首先, 设计了一个基本的AST访问者类ASTVisitorBase, 包含对程序源代码AST上各种节点进行访问的成员虚函数VisitX, 然后实现了Traverse成员函数, 在对AST进行递归式遍历的同时调用VisitX函数来对AST上的每个节点进行访问, 其中X可以是任意类型的节点, 例如访问声明Decl的函数VisitDecl和访问语句Stmt的函数VisitStmt等. 然后, 设计了一个实现插桩的AST访问者类ASTVisitor, 继承于ASTVisitorBase, 并对其中的成员虚函数VisitX进行虚函数重载, 实现源代码插桩功能.
Movec的使用非常简便. 用户只需要执行3个命令即可得到检测结果: 运行Movec对源代码进行自动插桩; 运行编译器将插桩后的源代码编译为可执行程序; 运行插桩后的可执行程序得到检测结果. 例如,
实例1的检测结果
实例2的检测结果
Movec可以被用于C程序设计语言的教学, 有效提高教学效果. 首先, 学生可以对自己编写的程序运行Movec, 更快地找到程序中的内存错误, 极大地缩短调试时间, 提高学习效率. 通过长期使用Movec, 学生能养成正确运用指针和内存操作的习惯, 提高编程能力. 第二, Movec的错误检测函数库可以作为C语言的演示系统, 帮助学生掌握C语言中一些复杂的理论知识. 函数库的实现不仅大量使用了基本的条件语句、循环语句、数组、函数等, 还覆盖了较为复杂的指针和内存操作、结构体和链表等知识. 例如, 指针元数据采用结构体实现, 并包含了指向状态信息节点的指针; 指针元数据表采用基于动态内存分配的哈希表实现, 并采用链表来处理哈希冲突. 这可以帮助学生深入理解这些理论知识, 并掌握如何将这些知识正确地运用到编程实践中.
Movec可以被用于面向对象程序设计语言(C++)的教学, 有效提高教学效果. Movec的源代码自动插桩模块可以作为C++语言的演示系统, 帮助学生掌握C++语言中一些抽象的理论知识. 插桩模块的实现覆盖了重要但抽象的封装、继承和多态等知识. 例如, AST中所有的语法节点类型都采用了封装的类来实现, 并且采用继承来描述相关节点类型之间的联系; 递归式AST访问者的实现也采用了封装、继承和多态, 即继承于一个基本的AST访问者类, 并对其中的AST节点访问函数进行虚函数重载; 通过这些设计改善了大规模代码的模块化、可维护性、可复用性和健壮性. 这可以帮助学生深入理解这些面向对象特性的优点, 并主动地将这些知识合理地运用到编程实践中.
Movec也可以作为数据结构、编译原理、软件工程、软件测试等课程的案例分析材料, 全面贯穿计算机、软件工程等专业的培养计划.
程序设计是计算机、软件工程等工科专业的第一门核心必修专业课程. 熟练地掌握程序设计技能不仅是学习后续专业课程的基础, 也是获得理想工作机会的重要条件. 笔者在教学实践中发现, 已有的教学系统只支持网络教学组织[
叶冬芬, 杨明霞, 方智敏. 基于B/S的《C程序设计》网络教学系统. 计算机系统应用, 2016, 25(4): 56–62.
罗荣良, 吴明晖. 基于“MOOC+实验辅助平台”的面向对象程序设计教学实践. 计算机教育, 2020, (2): 170–174.
王金鹏, 曹旗磊, 王涵. 基于Online Judge的程序设计基础教学改革与实践. 计算机教育, 2020, (2): 101–104.
李旻朔, 林巧. 多核平台上程序在线评测辅助教学系统. 计算机系统应用, 2011, 20(6): 129–132.
韩志科, 王贵, 韩俊杰. 基于API自动测试的程序设计在线判题系统的研究与实现. 计算机系统应用, 2008, 17(7): 9–13.
et al. Beyond spatial and temporal memory safety. Proceedings of ACM/IEEE 40th International Conference on Software Engineering. Gothenburg, Sweden. 2018. 189–190.]]>
Chen Z, Gu Y, Huang ZQ,
et al. Parametric runtime verification of C programs. Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Eindhoven, the Netherlands. 2016. 299–315.]]>
et al. AddressSanitizer: A fast address sanity checker. Proceedings of the 2012 USENIX Annual Technical Conference. Berkeley, CA, USA. 2012. 28.]]>
et al. Runtime verification of memory safety via source transformation. Proceedings of ACM/IEEE 40th International Conference on Software Engineering: Companion. Gothenburg, Sweden. 2018. 264–265.]]>