基于多核CPU的运行时验证技术的研究与实现
2018-06-11王丰，印钊
王 丰，印 钊
（武汉邮电科学研究院湖北武汉430074）
随着信息技术的不断发展，软件开发周期越来越短，如何快速有效地检验软件的可靠性成为一个重要问题。运行时验证技术是一种软件测试技术，其思想是通过持续监控并采集程序运行状态信息来验证软件运行是否符合规范。早期的运行时验证技术受限于单核处理器（Central Processing Unit，CPU）的性能不足，使用其测试软件会影响目标软件的运行速度，导致测试效率降低、测试成本增加。近几年多核CPU电脑已经大规模普及，研究基于多核CPU的运行时验证技术对于改进传统的运行时验证技术尤为重要。
本文在基于多核CPU的Ubuntu平台上，对两个不同的开源程序针对数组引用越界这种软件错误进行运行时验证技术的研究。通过实验数据得出了基于多核CPU的运行时验证技术能够有效提高监控软件效率、增加软件可靠性的结论。
1 相关技术概述
1.1 运行时验证技术
验证技术是一种检验系统的行为是否符合规范的技术，主要的验证技术有定理证明、模型检测和测试3种[1]。定理证明和模型检测主要从宏观层面通过公式推导和建模来验证系统的正确性，但一个正确的系统运行之后仍可能出现一些无法预料的错误，这就需要通过测试的方法，从微观层面检验系统的正确性。运行时验证技术是一种测试方法[2]。该技术的思想是：运行程序前对软件进行相关配置，设计一个监控器，如果程序在运行过程中出现了不符合规范的异常，监控器能够实时记录和汇报软件运行状况。运行时验证技术具有易于部署、可降低软件测试的成本、可提高软件测试效率等优点。
运行时验证技术一般通过插桩的方法来实现。插桩是在程序源代码中插入一段自定义的代码，这段自定义的代码的作用是收集记录源程序的运行信息，比如数组引用情况、指针引用情况、函数的调用情况等评估程序运行状态的重要指标。插入的自定义代码叫做桩代码，桩代码不能影响程序结果，也不能破坏程序执行逻辑的完整性[3]。由于桩代码需要实现信息获取与传递功能，在运行程序时必然会占用系统资源、增加运行时间，这就是使用运行时验证技术所带来的性能损耗。
1.2 多核CPU与并行编程
CPU是一台计算机的运算核心和控制核心。它的功能主要是解释计算机指令以及处理计算机软件中的数据[4]。目前常用的多核CPU通常指的是单芯片多处理器（Chip Multiprocessors，CMP）。CMP的思想是将大规模并行处理器中的对称多处理器集成到同一芯片内，各个处理器并行执行不同的进程[5]。这种依靠多个CPU并行地运行程序的方式被称为并行处理。并发和并行是两个常用的计算机概念。并发是指当有多个线程在操作，而系统只有一个CPU时，宏观上有多个程序在同时运行，但微观上这些程序只是串行地交替执行，在同一时刻只能有一个程序被执行[6]。并行是指当系统有不止一个CPU时，不同的线程可以在不同的CPU上执行，线程之间互不占用CPU资源，属于真正的同时运行。
进程是系统进行资源分配和调度的基本单位，一个进程可以分为两个部分：线程集合和资源集合。线程是进程中的一个动态对象，进程中的所有线程将共享进程里的资源。实现基于多核CPU的运行时验证技术需要使用线程并行的编程技术。线程并行编程的主要内容是解决共享内存、消息传递和数据并行这3个方面的问题。本文使用POSIX threads线程库，简称Pthreads线程库[7]，进行线程的相关操作。Pthreads线程库是Linux系统中多线程编程的标准库。与大多数线程库的功能相似，Pthreads线程库具有线程的创建和终止、线程同步、设置条件变量与信号量等功能[8]。
1.3 数组越界
缓存溢出是一种输入数据超出缓存区大小的程序错误，可导致程序运行出错或者崩溃[9]。数组是程序中最常用的一种缓存区，函数调用数组的数组名出错、调用数组的下标超过了数组定义的大小等错误被称为“数组越界”。数组越界是一种缓存溢出的表现，是一种常见的程序错误。本文通过检验数组越界这一错误来证明运行时验证技术的有效性。
2 基于多核CPU的运行时验证技术的设计
本文的设计思想是：设置两个线程，一个线程负责运行目标程序，另一个线程负责监控目标程序运行状况，在运行目标程序之前，修改目标程序的源代码，在源代码中插入负责监控的桩代码。为了模拟程序运行时出现错误，使用数组越界这种错误作为各种程序错误的代表。最后在其他条件相同的情况下使用单核CPU和多核CPU进行对比实验，得到实验结果和结论。下面是相关步骤的具体设计。
本文的实验需要创建两个线程：一个目标程序线程，一个监控器线程。在目标程序运行的过程中，监控器线程负责定时收集程序运行信息。一般的多核CPU系统能够自动分配线程给不同的核心，但如果使用核绑定技术将目标程序线程和监控器线程分别绑定到用户自定义的处理器核心上可以使效率更高。监控器线程如果一直处于运行状态，会占用系统资源，导致目标程序性能降低，因此需要根据目标程序使用数组的次数来决定是否唤醒监控器线程，本次实验把使用数组次数设为3000。每使用3000次数组，就唤醒监控器线程来处理信息，判断这3000次数组使用中是否出现了数组越界的错误。监控器线程在对这些数据进行处理的过程中，会将每一个数据的处理结果写入文件。故监控器线程的工作流程为：
1）监控器线程检测目标程序进程是否使用数组，不是则休眠，使用数组则进入下一步；
2）记录使用的数组信息，计数number（初始为0）加1；
3）number是否等于3000，等于则进入下一步，小于则返回第1步；
4）监控器线程集中处理之前收集的3000次数组的数据，处理完成后number清零。
5）结束。
两个线程之间的通信使用一个结构体数组来实现。下面是两个线程用来通信的全局结构体数组的定义：
该结构体传递的信息是目标程序运行中用到的数组下标。这里定义一个全局整形变量number作为结构体数组的下标。本次实验希望通过运行时验证技术来检验数组越界这一错误。检验数组是否越界的方法为：目标系统运行过程中，每次使用数组的信息都被会用结构体数组communication[i]里保存。获取结构体数组下标的最大值、最小值和下标值subscript，如果使用的数组的下标subscript比min小或者比max大，那么可以认为目标程序运行过程中发生了数组越界的错误。每次目标程序调用一次数组就把结构体数组的信息存入一个文件中，按顺序分配行号和列号，如图1所示。
图1 保存使用过的数组信息
如果检测到发生数组越界的错误，那么将出错的数组的行号列号存入到“error.txt”文件里。如图2所示。
运行时验证技术对不同程序的验证效率是不同的，为了得出更严谨的结论，本次实验使用PPETS math functions和Qsort两个开源目标程序进行对比实验。PPETS math functions是一款是计算的软件，具有计算量大，运行时间较长，大量使用数组的特点。
图2 保存产生错误的数组信息
Qsort程序是编译器自带的快速排序程序，通过调用math.h头文件中的qsort（）函数，程序会使用快速排序算法对数据进行排序，Qsort程序的代码规模与复杂度远小于PPETS math functions程序。
本次实验把目标程序的执行时间作为运行时验证技术的性能判定的参考值，在其他条件相同的情况下，程序执行时间越短表示性能越好。在Linux操作系统下，可以通过time命令来获取一个程序的执行时间。
为了证明多核CPU能够加速实现运行时验证技术，本次实验设计5种场景：
1）单核平台下直接运行目标程序；
2）单核平台下使用运行时验证技术，运行目标程序；
3）多核平台下直接运行目标程序；
4）多核平台下不进行核绑定，使用运行时验证技术，运行目标程序；
5）多核平台下进行核绑定，使用运行时验证技术，运行目标程序。
3 基于多核CPU的运行时验证技术的实现
本次实验使用的处理器为Intel酷睿i3-5005U，CPU主频2 GHz，双核心，操作系统是Linux Ubuntu，编程语言为C语言。实验通过编写代码并运行得到实验结果，实现本次实验的关键就是插桩代码和线程控制的代码。
3.1 插桩代码
本次实验两个目标程序PPETS math functions和Qsort都是可以直接运行的，因此需要在目标程序中插入作为记录程序运行信息的桩代码，如下所示：
以上代码的作用是如果目标程序运行时使用了数组，通过调用aStake（）桩函数，将使用的数组的元素x[i]的下标最小值1、最大值2、下标i、存储的文件名"test.txt"和存储在文件中第3行第4列6个实参传递给结构体数组。
由于目标程序PPETS math functions和Qsort都是非常成熟的程序，一般情况很难出现运行错误。为了模拟目标程序出现运行时错误，实验需要随机产生一些越界的数组下标。调用
3.2 线程控制代码
实验新建一个监控器线程并将其与一个CPU进行核绑定，将目标程序与另一个CPU进行核绑定，这样就能发挥多核CPU的优势，达到监控程序与目标程序并行运行的效果。使用Pthreads线程库提供的pthread_create（）函数创建线程。Linux系统提供了调用函数来设置核亲和性：sched_setaffinity（pid_t pid，unsigned int cpusetsize，cpu_set_t*mask），参数pid是目标线程或进程的id（若为0表示当前线程）；参数cpusetsize指后一个参数mask所指向的内存结构对象的大小；指针参数mask指向类型为cpu_set_t的对象。模拟单核CPU运行程序只需把所有进程都放在一个核心上运行即可。
以下是监控器线程功能实现代码：
图3是多核平台下把两个线程绑定到不同的CPU成功的结果。
图3 不同线程核绑定成功
4 实验结果
正如设计中提到的，本次实验有5种场景：
1）单核平台下直接运行目标程序；
2）单核平台下使用运行时验证技术，运行目标程序；
3）多核平台下直接运行目标程序；
4）多核平台下不进行核绑定，使用运行时验证技术，运行目标程序；
5）多核平台下进行核绑定，使用运行时验证技术，运行目标程序。
实验对每种场景都进行了多次实验，最终结果取多次实验结果的平均值[10-18]。
图4是目标程序为Qsort，运行场景1的一次结果，其中real时间是程序运行时间，实验结果以real时间为参考。
图4 PPETS math functions单核直接运行结果
图5显示的是目标程序为PPETS math functions的5种实验场景的平均结果，其中场景1的运行时间为40.7 s，场景2的运行时间为42.2 s，场景3的运行时间为33.3 s，场景4的运行时间为35.1 s，场景5的运行时间为31 s。
图5 目标程序为PPETS math functions的实验结果
对于Qsort软件中也对上述5种情况分别进行了实验，图6为实验结果。其中场景1的运行时间为18.9 s，场景2的运行时间为23.4 s，场景3的运行时间为17.1 s，场景4的运行时间为20.5 s，场景5的运行时间为17.9 s。
图6 目标程序为Qsort的实验结果
通过对比以上实验结果，可以得出以下实验结论：
1）运行同一个目标程序，无论是使用运行时验证技术还是直接运行，多核运行速度都比单核运行速度快。目标程序为PPETS math functions时，多核运行速度（未绑定核）比单核运行速度平均快17.5%，核绑定的情况下多核运行速度比单核运行速度平均快26.5%。目标程序为Qsort时，多核运行速度（未绑定核）比单核运行速度平均快10.9%，核绑定的情况下多核运行速度比单核运行速度平均快23.5%；
2）运行同一个目标程序，无论是单核还是多核，使用运行时验证技术都会增加程序运行时间。目标程序为PPETS math functions时，时间平均增加了4.5%，目标程序为Qsort时，时间平均增加了21.8%；
3）运行同一个目标程序，多核运行时进行核绑定能够在多核运行原先的基础上进一步提高性能。目标程序为PPETS math functions时，核绑定之后速度提高11.7%。目标程序为Qsort时，核绑定之后速度提高12.7%；
4）对于不同的目标程序，目标程序规模越大，使用运行时验证技术占用资源的比例就越少，软件测试效率越高。
5 结束语
本文通过对相关技术的研究与分析，实现了基于多核CPU的运行时验证技术并进行了实验。分析实验结果可以得出结论：与基于单核CPU的运行时验证技术相比，本文所实现的基于多核CPU的运行时验证技术能够有效提高软件的测试效率和运行速度，具有一定的实用价值。当然本文的设计还存在需要改进和完善的地方，比如插桩代码和插桩的位置还可以进行优化，使得运行时验证技术造成的损耗降低；监控器线程的功能还可以增加，使其能够检验多种软件运行错误。这些是今后需要研究和关注的方向。
