陈韬 王明明

摘   要：Linux操作系统、嵌入式系统、航电系统、通信系统等一般都是用C/C++语言进行编写。因为C语言具有偏底层硬件、移植性强、执行效率高等优秀特性。但是随着多核并行机的出现，许多语言也开始支持多线程编程。由于C语言本身存在着对内存访问时，不对内存边界进行检查的问题，从而造成软件系统相关的可靠性和安全性问题。对多线程C语言程序来说，由于多线程程序的不确定性，使得运行时验证多线程C程序的内存安全问题变得更加困难。通过使用基于改进的指针运行时验证技术、多核多线程技术、并行计算、无锁数据结构技术、源代码插桩技术方法，并结合开源工具Clang编译器实现原型工具Movec对多线程C程序的支持。该工具实现了对多线程C程序内存安全问题的运行时验证。然后通过Mibench和SARD测试用例进行实验，验证了该工具对多线程C程序进行运行时验证的有效性。

关键词：多线程;多核;无锁数据结构;运行时验证;源代码插桩;编程语言

中图分类号：TP316.2                                          文献标识码：A

Memory Security Runtime Verification for Multi-threaded Programs

CHEN Tao？覮，WANG Ming-ming

（Department of Computer Science and Technology， Nanjing University of Aeronautics

and Astronautics，Nanjing，Jiangsu 211106，China）

Abstract：Linux operating system，embedded system，avionics system，communication system are usually written in C/C++ programming language. Because of the excellent features of the C language，which has a low level of hardware，strong portability and high execution efficiency. But with the advent of multicore parallel machines，many languages have also begun to support multi-threaded programming. C language has the problem that it does not check memory boundary when accessing memory，which causes the reliability and security of software system can not be guaranteed. For multithreaded C language programs，it is difficult to verify the multithreading C program at run time because of the uncertainty of multithreaded programs. we use improved pointer runtime verification，multicore and multi thread technology，parallel computing，unlocked data structure technology，the aid of open-source compiler Clang and source code instrumentation technology complete the prototype tool Movec（Monitoring，verification and control） which supports multithreading C programs runtime verification. Then，By experimentation on Mibench and SARD，it is verified that the tool can indeed run time validation for multithreaded C programs.

Key words：multi thread;multicore;unlocked data structure;runtime verification;source code piling;programming language

在科技智能化不断发展的今天，计算机的软件和软件系统在信息化时代起着极为关键的作用。这就使得软件的可靠性要求越来越高。软件运行时的验证技术[1-4]就是一种轻量级的新型自动化验证技术。由于运行时验证技术是在程序运行过程中进行验证的技术，所以它能保证验证程序的实时性。另外，多核的到来使得多线程变成了真正意义上的并行运行，即每个处理器运行不同的线程，同一时刻多个处理器同时运行程序。现在多线程程序应用越来越广泛，主流的语言C、C++、JAVA、PHP等基本都支持多线程编程。近年来，关于运行时验证技术的运用已经越来广泛，其中比较成熟的工具有Java-MOP、Enforce-MOP、Software Cruising、RiTHM等。Java-MOP实现了对java程序进行运行时验证。RiTHM是一种以时间为触发机制的验证工具。Enforce-MOP则是用来运行时验证多线程Java程序的工具。它是对Java-MOP工具的一个改进，使得该工具支持处理多线程的Java程序。Software Cruising是用来解决并行程序堆缓冲区溢出问题的技术。而C语言是一种更加接近底层的硬件的语言，具有执行率高，可移植性强的特点。但是该语言在对内存访问时，不对内存边界进行检查，就可能会导致软件出现内存安全漏洞[5-6]。如果是多线程的C语言程序，由于多线程運行的不确定性，更有可能会导致内存安全问题。

多线程程序的运行时验证原理。解决办法是采用基于指针技术[10-11]对程序中所有的内存进行验证分析。原型工具Movec对于C程序内存安全性运行时验证的解决方法。其中Movec主要功能是检测单线程C程序中内存安全性问题。检测的内存错误类型分为空间内存安全问题和时间内存安全问题。空间内存安全指的是数组越界，指针访问的内存越界，指针未初始化等内存安全性问题。该问题主要通过指针元数据的上下界进行判定。时间内存安全问题主要是申请的内存空间多次释放问题，该问题主要是通过指针元数据中对象存储状态进行判定。基于指针技术方法通过对程序中指针构造对应的指针元数据，该指针元数据记录了该指针对象的上下界和存储情况并存储在了哈希表中。在指针进行赋值或者参数传递时对指针元数据进行更新和替换，针对源代码中所有的指针进行指针元数据的存取，通过元数据的信息进行内存安全性的检测。待监控程序的主线程分别创建了两个子线程，每个线程都有自己的事件序列并且每个序列都会触发与之相关的响应操作。如果我们还是采用单线程情况下的办法去解决内存安全性问题的话，那么在如图1所示的情况下，由于多线程并行运行的特性，事件2，事件3和事件4會同时对一块地址的元数据进行读和删除操作。在多线程情况下，事件序列就变得不确定了。在多核的情况下，每个线程是运行在单独立的处理器上，可以并行的处理问题，所以导致了可能会出现对同一个内存进行同步访问的情况。多线程程序引起最多的问题就是资源竞争问题，内存安全性验证本质上也是存在对指针元数据操作时的资源竞争问题。对此本文使用无锁并行的数据结构存储指针元数据。

通过设计验证工具完成了对多线程C程序内存安全的动态监控。主要工作如下：

1.提出多线程程序的运行时验证原理。

2.结合无锁技术[7-9]，实现了基于无锁的数据结构。

3.通过多线程的插桩算法和Clang编译器实现了多线程程序内存安全运行时验证工具。

4.使用该工具和SoftBoundCets、Crusier工具进行有效性对比实验，然后通过MiBench、SARD开源测试集进行性能实验。最后得出结论。

1   无锁数据结构设计

在高性能并发运行的机器中，需要支持并发操作的哈希表。为了解决这些问题我们通过使用原子操作CAS（compare and swap）完成了在多线程下并发操作的无锁哈希表数据结构。哈希表由两部分组成一部分是包含桶元素和项元素的链表，另一部分是包含指针的可扩展数组。

1.1   无锁有序链表

查找操作执行过程中保证*pre是指向链表的结点，然后将pre指向pcur的结点。第一步判断cur是否为空，如果为真的话，那么在这个时候链表中所有的值都是小于查找值的，并且返回0，表示没有找到该结点。否则的话执行第二步在cur ！= null且结点标记mark为0时，首先将当前结点的下一个结点存储下来，然后判断cur.key是否大于或等于查找值。如果判断结果为真，在ckey值等于查找值时返回1，表示已经在链表中找到该结点，在ckey值不等于查找值时返回0，表示链表中没有找到该结点。如果判断结果为假时，将当前结点指向存储的下一个结点继续执行。在查询过程中如果遇到结点的mark值为1时，表示该结点是需要删除的结点，需要通过CAS原子操作删除结点。

1.2   可扩充哈希表

在无锁链表的基础之上，本文实现了支持多线程并行操作的无锁哈希表。该算法主要思想是：不是通过在哈希桶插入项，而是在存储项的链表里面插入哈希桶元素。

插入函数创建一个新的结点并赋值一个需要插入的值。so_regularkey函数作用是把key值的二进制逆转并在最右位设为1。桶元素的下标是由key对size取余后得到。首先判断桶元素有没有被初始化，如果没有初始化就会调用initialize_bucket函数初始化桶元素。否则该结点就会调用无锁链表中的insert函数将新创建的结点插入到无锁链表中。如果插入操作成功，就可以使用fetch_and_inc函数对项数量进行计数。该函数是一个原子性操作。最后检查项数量有没有超过哈希表的过载因子。如果超过过载因子，就会将哈希表的大小拓展为原来的两倍。扩展的方式是将二维桶元素数组进行对应的初始化。

查找函数首先确保查找值对应的桶元素已经被初始化，然后调用无锁链表中的find函数。List_find函数不是直接遍历整个链表，而是通过计算得到的桶元素指向虚结点去遍历虚结点之后的项元素，最后找到大于或等于该值的最小结点。

删除函数也要保证删除值对应的桶元素已经被初始化，如果没有初始化就调用initialize_bucket函数。然后调用无锁链表中的delete函数。如果删除成功也要调用fetch_and_dec函数去减少桶项数量。fetch_and_dec函数也是一个原子性操作。

2   多线程程序内存安全运行时验证工具

实现

2.1   插桩算法

结合Clang编译器的源代码插桩技术和无锁哈希表对原型工具Movec进行多线程的支持。该工具先是对C语言多线程程序进行词法分析、语法分析、生成语法树，然后对语法树进行遍历，对pthread库的函数调用进行包装，将包装好的程序替换掉源程序中的Pthread库函数调用，并生成支持多线程操作的无锁哈希表。对源代码中涉及的内存地址操作，如对象创建、函数调用、对象释放或对象赋值等，将指针元数据的操作函数插入到代码的固定位置。然后生成插桩后的C程序，最后运行插桩后的C程序检测多线程情况下内存安全错误。对于Clang编译器，在通过RecursiveASTVisitor的VisitFunctionDecl方法访问抽象语法树中的FunctionDecl类型节点时，会对函数定义的节点进行访问，通过重写VisitCallExpr函数。函数定义除了进行还对函数中涉及到内存访问的表达式进行了代码插桩，这里我们只介绍把main函数作为主线程进行多线程相关部分的插桩。

主函数的插桩算法是在主函数中进行无锁哈希表的初始化工作。对于哈希表中的线程使用函数，直接生成memsafe.c和memsafe.h文件，这两个文件包含了多线程C程序在进行内存安全验证时进行存储的无锁哈希表。

2.2   多线程读取哈希表

全局变量包含两个哈希桶元素数组指针是因为我们需要创建两个哈希表，一个存放函数元数据，一个存放指针元数据。哈希表是通过数组桶和无锁链表组成的。由于每个线程需要有私有的pre，pcur，pnext去独立的访问哈希表，所以每個线程都独自创建了私有的三个变量。我们在包装线程创建函数时，创建每个线程对应的私有值并记录每个线程的线程ID。每个线程通过自己创建的3个MarkPtrType类型去独立的访问哈希表中存储信息的无锁链表，避免线程之间访问时，对访问变量的竞争。哈希表中存放了void **value变量。通过定义二级指针的方式用来存储指针元数据和函数元数据，通过二级指针强制类型转化的方式，将void**分别转化为PREFIXpmd**和PREFIXfmd**。表1所示定义指针元数据和函数元数据.

3   实   验

3.1   哈希表性能分析

本小节主要工作是对哈希表对于内存安全的性能进行分析。第一部分在单线程的情况下将下面4种类型的哈希表进行数据对比。实验数据如图1所示。实验数据是由十次结果的平均值来获取的。其中A为使用数组和链表组成的哈希表，B为不支持并行操作的可扩展的哈希表;C为支持并发操作的哈希表，为A类型加入互斥操作而来;D为本文实现的哈希表。

图1中纵坐标代表着单线程程序进行哈希表存取的运行时间。由此可以看出单线程情况下B哈希表的时间是A哈希表的4倍左右，D哈希表的时间是C可扩展哈希表的四倍左右。这是因为本文设计的哈希表D和可扩充的哈希表B是存储在无锁有序的链表之中。而一般的哈希表存储时数组链接的链表只是用来处理哈希冲突的，链表不一定需要有序。该原因使得单线程情况下采用可扩展的哈希表结构，性能有所降低。

第二部分，由于A哈希表和B哈希表没有进行并行的设计所以无法进行多线程情况下，哈希表的存取操作。数据如图2所示。

图2中纵坐标的单位是微秒。代表着多线程程序运行的时间。本文所设计的可扩展哈希表D在线程数增加时，哈希表的时间没有增加。而B哈希表的时间随着线程数的增加而增加。这是应为，B在哈希表进行扩展的时候，首先需要扩展哈希表容量，然后将原来哈希表中的值重新存储到扩展之后的哈希表。在此期间，其它线程时无法进行哈希表存取的，从而导致B哈希表的性能因为线程的增加而变差。

3.2   多线程C程序内存安全的有效性实验和性能

实验

由于需要检测C程序的内存安全问题，所以我们需要对不同的内存安全类型进行检测。为此我们使用SARD（Software Assurance Reference Datase）作为多线程的C语言进行内存安全的测试集。然后将本文的工具和SoftBoundCets[12-13]工具、Cruiser[14]工具进行比较。实验结果如表2所示。SoftBC指SoftBoundCets，Cru指Cruiser。

表2   Movec、SoftBoundCets、Cruiser对比

表2中Yes表示能检测出所有线程以及该线程存在的内存安全错误，No表示不能检测出所有线程的内存安全错误。通过使用多个线程，并且每个线程运行不同的错误类型来比较工具对多线程、多内存错误类型的有效性判定。由表可知SoftBoundCets仅支持单线程下内存安全性问题的判定;Cruiser支持单线程和多线程关于堆内存内存安全的判定。而我们设计拓展的Movec工具可以支持单线程和多线程下多种内存安全的判定。该表说明本文的工具在有效性上要比SoftBoundCets、Cruiser工具好。支持的范围更广。

另外本文使用该工具直接对SARD中的多线程C程序进行验证实验结果如表3所示。表中的数据代表着程序运行的时间，单位是微妙/us。

表3说明该工具可以有效的对开源测试集进行源代码插桩，并正确的运行插桩之后的程序。

由于C语言主要的应用领域是嵌入式平台，而却随着嵌入式硬件系统的不断升级，多线程的C程序在嵌入式平台也变的越来越常见，所以本节剩余部分，通过嵌入式平台的应用程序对Movec的性能进行分析。其中MiBench一共包括35个程序，分别由通信，网络，安全，电子消费、工业制造和办公自动化六个部分组成。每个应用包含源文件、MakeFile文件和配置文件。通过选取其中的Dijkstra（small）、Dijkstra（large）、CRC32、basicmath（small）、basicmath（large）这三个部分进行实验。实验结果如表6所示，表中的时间单位为秒/s，代表着多线程程序运行的时间，表中的数据为10次运行之后，统计时间的平均值。

4   结   论

介绍对多线程程序进行运行时验证[15]的

原理，对于多核程序该如何处理各个事件序列。然后主要介绍对于无锁哈希表设计模式和实现算法，其中哈希表中内容主要存储在无锁的链表中，并介绍支持多线程操作的查询，插入，删除的无锁链表，在此基础上设计可扩展的哈希表。通过设计插桩算法和clang编译器完成支持多线程程序的运行时验证的工具Movec[16]。最后通过在多线程和单线程情况下分析哈希表的性能;将设计后的Movec与SoftBoundCets、Cruiser进行有效性的对比实验得出本文设计的工具更适合对于多线程程序的内存安全监测;并使用开源测试集SARD和Mibench进

行性能分析实验。接下来的工作主要是以下几个方面：

（1）结合静态分析技术，减少C程序中不必要的一些插桩

（2）在原有的数据结构存储结构上进行优化，提高数据查找的速度

（3）将源代码的插桩过程分配到不同的处理器核心上，提高Movec工具编译运行的性能。

参考文献

[1]    CHEN Z，WANG Z，ZHU Y，et al. Parametric runtime verification of C programs[C]//International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer Berlin Heidelberg，2016： 299—315.

[2]   MEREDITH P O N，JIN D，GRIFFITH D，et al. An overview of the MOP runtime verification framework[J]. International Journal on Software Tools for Technology Transfer，2012，14（3）： 249—289.

[3]   LEUCKER M，SCHALLHART C. A brief account of runtime verification[J]. The Journal of Logic and Algebraic Programming，2009，78（5）： 293—303.

[4]   MACNAMEE C，HEFFERMAN D. On-chip  instrumentation for runtime verification in deeply embedded processors[C]//2015 IEEE Computer Society Annual Symposium on VLSI. IEEE，2015： 374—379.

[5]   DURUMERIC Z，KASTEN J，ADRIAN D，et al. The matter of heartbleed[C]//Proceedings of the 2014 Conference on Internet Measurement Conference. ACM，2014： 475—488.

[6]   COWAN C，WAGLE P，PU C，et al. Buffer overflows： attacks and defenses for the vulnerability of the decade[C]// DARPA Information Survivability Conference and Exposition，2000. DISCEX′00. Proceedings. IEEE，2002，2：119—129.

[7]   GIACOMONI J，MOSELEY T，VACHHARAJANI M. FastForward for efficient pipeline parallelism： a cache-optimized concurrent lock-free queue[C]// ACM Sigplan Symposium on Principles and Practice of Parallel Programming. ACM，2008：43—52.

[8]   MICHAEL M M. High performance dynamic lock-free hash tables and list-based sets[C]// Fourteenth ACM Symposium on Parallel Algorithms and Architectures. ACM，2002：73—82.

[9]   LEE P P C，TIAN B，CHANDRANMENON G. A lock-free，cache-efficient multi-core synchronization mechanism for line-rate network traffic monitoring[C]//IEEE International Symposium on Parallel & Distributed Processing. IEEE，2010：1—12.

[10] AUSTIN T M，BREACH S E，SOHI G S. Efficient detection of all pointer and array access errors[C]// Proc. '94 Conference on Programming Language Design and Implementation. 1994：290—301.

[11] OIWA Y. Implementation of the memory-safe full ANSI-C compiler[C]//ACM Sigplan Notices. acm，2009，44（6）： 259—269.

[12]  LUk C K，HONG S，KIM H. Qilin： exploiting parallelism on heterogeneous multiprocessors with adaptive mapping [C]// In Micro-42： Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture. New York，NY，USA，2009： 45—55.

[13]  NAGARAKATTE S，ZHAO J，MARTIN M M K，et al. CETS： compiler enforced temporal safety for C[C]//ACM Sigplan Notices. ACM，2010，45（8）： 31—40.

[14]  ZENG Q，WU D，LIU P. Cruiser：concurrent heap buffer overflow monitoring using lock-free data structures[J]. Acm Sigplan Notices，2011，46（6）：367—377.

[15]  張硕，贺飞. 运行时验证技术的研究进展[J].计算机科学，2014，41（ 11） ： 359—363.

[16]  王哲民，陈哲，朱云龙，等. 参数化运行时验证研究和工具实现[J]. 小型微型计算机系统，2016，37（12）：2667—2672.