面向多線程程序的內(nèi)存安全運行時驗證

陳韜 王明明

摘 ? 要：Linux操作系統(tǒng)、嵌入式系統(tǒng)、航電系統(tǒng)、通信系統(tǒng)等一般都是用C/C++語言進行編寫。因為C語言具有偏底層硬件、移植性強、執(zhí)行效率高等優(yōu)秀特性。但是隨著多核并行機的出現(xiàn)，許多語言也開始支持多線程編程。由于C語言本身存在著對內(nèi)存訪問時，不對內(nèi)存邊界進行檢查的問題，從而造成軟件系統(tǒng)相關(guān)的可靠性和安全性問題。對多線程C語言程序來說，由于多線程程序的不確定性，使得運行時驗證多線程C程序的內(nèi)存安全問題變得更加困難。通過使用基于改進的指針運行時驗證技術(shù)、多核多線程技術(shù)、并行計算、無鎖數(shù)據(jù)結(jié)構(gòu)技術(shù)、源代碼插樁技術(shù)方法，并結(jié)合開源工具Clang編譯器實現(xiàn)原型工具Movec對多線程C程序的支持。該工具實現(xiàn)了對多線程C程序內(nèi)存安全問題的運行時驗證。然后通過Mibench和SARD測試用例進行實驗，驗證了該工具對多線程C程序進行運行時驗證的有效性。

關(guān)鍵詞：多線程;多核;無鎖數(shù)據(jù)結(jié)構(gòu);運行時驗證;源代碼插樁;編程語言

中圖分類號：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

在科技智能化不斷發(fā)展的今天，計算機的軟件和軟件系統(tǒng)在信息化時代起著極為關(guān)鍵的作用。這就使得軟件的可靠性要求越來越高。軟件運行時的驗證技術(shù)[1-4]就是一種輕量級的新型自動化驗證技術(shù)。由于運行時驗證技術(shù)是在程序運行過程中進行驗證的技術(shù)，所以它能保證驗證程序的實時性。另外，多核的到來使得多線程變成了真正意義上的并行運行，即每個處理器運行不同的線程，同一時刻多個處理器同時運行程序?，F(xiàn)在多線程程序應(yīng)用越來越廣泛，主流的語言C、C++、JAVA、PHP等基本都支持多線程編程。近年來，關(guān)于運行時驗證技術(shù)的運用已經(jīng)越來廣泛，其中比較成熟的工具有Java-MOP、Enforce-MOP、Software Cruising、RiTHM等。Java-MOP實現(xiàn)了對java程序進行運行時驗證。RiTHM是一種以時間為觸發(fā)機制的驗證工具。Enforce-MOP則是用來運行時驗證多線程Java程序的工具。它是對Java-MOP工具的一個改進，使得該工具支持處理多線程的Java程序。Software Cruising是用來解決并行程序堆緩沖區(qū)溢出問題的技術(shù)。而C語言是一種更加接近底層的硬件的語言，具有執(zhí)行率高，可移植性強的特點。但是該語言在對內(nèi)存訪問時，不對內(nèi)存邊界進行檢查，就可能會導(dǎo)致軟件出現(xiàn)內(nèi)存安全漏洞[5-6]。如果是多線程的C語言程序，由于多線程運行的不確定性，更有可能會導(dǎo)致內(nèi)存安全問題。

多線程程序的運行時驗證原理。解決辦法是采用基于指針技術(shù)[10-11]對程序中所有的內(nèi)存進行驗證分析。原型工具Movec對于C程序內(nèi)存安全性運行時驗證的解決方法。其中Movec主要功能是檢測單線程C程序中內(nèi)存安全性問題。檢測的內(nèi)存錯誤類型分為空間內(nèi)存安全問題和時間內(nèi)存安全問題?？臻g內(nèi)存安全指的是數(shù)組越界，指針訪問的內(nèi)存越界，指針未初始化等內(nèi)存安全性問題。該問題主要通過指針元數(shù)據(jù)的上下界進行判定。時間內(nèi)存安全問題主要是申請的內(nèi)存空間多次釋放問題，該問題主要是通過指針元數(shù)據(jù)中對象存儲狀態(tài)進行判定?；谥羔樇夹g(shù)方法通過對程序中指針構(gòu)造對應(yīng)的指針元數(shù)據(jù)，該指針元數(shù)據(jù)記錄了該指針對象的上下界和存儲情況并存儲在了哈希表中。在指針進行賦值或者參數(shù)傳遞時對指針元數(shù)據(jù)進行更新和替換，針對源代碼中所有的指針進行指針元數(shù)據(jù)的存取，通過元數(shù)據(jù)的信息進行內(nèi)存安全性的檢測。待監(jiān)控程序的主線程分別創(chuàng)建了兩個子線程，每個線程都有自己的事件序列并且每個序列都會觸發(fā)與之相關(guān)的響應(yīng)操作。如果我們還是采用單線程情況下的辦法去解決內(nèi)存安全性問題的話，那么在如圖1所示的情況下，由于多線程并行運行的特性，事件2，事件3和事件4會同時對一塊地址的元數(shù)據(jù)進行讀和刪除操作。在多線程情況下，事件序列就變得不確定了。在多核的情況下，每個線程是運行在單獨立的處理器上，可以并行的處理問題，所以導(dǎo)致了可能會出現(xiàn)對同一個內(nèi)存進行同步訪問的情況。多線程程序引起最多的問題就是資源競爭問題，內(nèi)存安全性驗證本質(zhì)上也是存在對指針元數(shù)據(jù)操作時的資源競爭問題。對此本文使用無鎖并行的數(shù)據(jù)結(jié)構(gòu)存儲指針元數(shù)據(jù)。

通過設(shè)計驗證工具完成了對多線程C程序內(nèi)存安全的動態(tài)監(jiān)控。主要工作如下：

1.提出多線程程序的運行時驗證原理。

2.結(jié)合無鎖技術(shù)[7-9]，實現(xiàn)了基于無鎖的數(shù)據(jù)結(jié)構(gòu)。

3.通過多線程的插樁算法和Clang編譯器實現(xiàn)了多線程程序內(nèi)存安全運行時驗證工具。

4.使用該工具和SoftBoundCets、Crusier工具進行有效性對比實驗，然后通過MiBench、SARD開源測試集進行性能實驗。最后得出結(jié)論。

1 ? 無鎖數(shù)據(jù)結(jié)構(gòu)設(shè)計

在高性能并發(fā)運行的機器中，需要支持并發(fā)操作的哈希表。為了解決這些問題我們通過使用原子操作CAS（compare and swap）完成了在多線程下并發(fā)操作的無鎖哈希表數(shù)據(jù)結(jié)構(gòu)。哈希表由兩部分組成一部分是包含桶元素和項元素的鏈表，另一部分是包含指針的可擴展數(shù)組。

1.1 ? 無鎖有序鏈表

查找操作執(zhí)行過程中保證*pre是指向鏈表的結(jié)點，然后將pre指向pcur的結(jié)點。第一步判斷cur是否為空，如果為真的話，那么在這個時候鏈表中所有的值都是小于查找值的，并且返回0，表示沒有找到該結(jié)點。否則的話執(zhí)行第二步在cur ！= null且結(jié)點標記mark為0時，首先將當前結(jié)點的下一個結(jié)點存儲下來，然后判斷cur.key是否大于或等于查找值。如果判斷結(jié)果為真，在ckey值等于查找值時返回1，表示已經(jīng)在鏈表中找到該結(jié)點，在ckey值不等于查找值時返回0，表示鏈表中沒有找到該結(jié)點。如果判斷結(jié)果為假時，將當前結(jié)點指向存儲的下一個結(jié)點繼續(xù)執(zhí)行。在查詢過程中如果遇到結(jié)點的mark值為1時，表示該結(jié)點是需要刪除的結(jié)點，需要通過CAS原子操作刪除結(jié)點。

1.2 ? 可擴充哈希表

在無鎖鏈表的基礎(chǔ)之上，本文實現(xiàn)了支持多線程并行操作的無鎖哈希表。該算法主要思想是：不是通過在哈希桶插入項，而是在存儲項的鏈表里面插入哈希桶元素。

插入函數(shù)創(chuàng)建一個新的結(jié)點并賦值一個需要插入的值。so_regularkey函數(shù)作用是把key值的二進制逆轉(zhuǎn)并在最右位設(shè)為1。桶元素的下標是由key對size取余后得到。首先判斷桶元素有沒有被初始化，如果沒有初始化就會調(diào)用initialize_bucket函數(shù)初始化桶元素。否則該結(jié)點就會調(diào)用無鎖鏈表中的insert函數(shù)將新創(chuàng)建的結(jié)點插入到無鎖鏈表中。如果插入操作成功，就可以使用fetch_and_inc函數(shù)對項數(shù)量進行計數(shù)。該函數(shù)是一個原子性操作。最后檢查項數(shù)量有沒有超過哈希表的過載因子。如果超過過載因子，就會將哈希表的大小拓展為原來的兩倍。擴展的方式是將二維桶元素數(shù)組進行對應(yīng)的初始化。

查找函數(shù)首先確保查找值對應(yīng)的桶元素已經(jīng)被初始化，然后調(diào)用無鎖鏈表中的find函數(shù)。List_find函數(shù)不是直接遍歷整個鏈表，而是通過計算得到的桶元素指向虛結(jié)點去遍歷虛結(jié)點之后的項元素，最后找到大于或等于該值的最小結(jié)點。

刪除函數(shù)也要保證刪除值對應(yīng)的桶元素已經(jīng)被初始化，如果沒有初始化就調(diào)用initialize_bucket函數(shù)。然后調(diào)用無鎖鏈表中的delete函數(shù)。如果刪除成功也要調(diào)用fetch_and_dec函數(shù)去減少桶項數(shù)量。fetch_and_dec函數(shù)也是一個原子性操作。

2 ? 多線程程序內(nèi)存安全運行時驗證工具

實現(xiàn)

2.1 ? 插樁算法

結(jié)合Clang編譯器的源代碼插樁技術(shù)和無鎖哈希表對原型工具Movec進行多線程的支持。該工具先是對C語言多線程程序進行詞法分析、語法分析、生成語法樹，然后對語法樹進行遍歷，對pthread庫的函數(shù)調(diào)用進行包裝，將包裝好的程序替換掉源程序中的Pthread庫函數(shù)調(diào)用，并生成支持多線程操作的無鎖哈希表。對源代碼中涉及的內(nèi)存地址操作，如對象創(chuàng)建、函數(shù)調(diào)用、對象釋放或?qū)ο筚x值等，將指針元數(shù)據(jù)的操作函數(shù)插入到代碼的固定位置。然后生成插樁后的C程序，最后運行插樁后的C程序檢測多線程情況下內(nèi)存安全錯誤。對于Clang編譯器，在通過RecursiveASTVisitor的VisitFunctionDecl方法訪問抽象語法樹中的FunctionDecl類型節(jié)點時，會對函數(shù)定義的節(jié)點進行訪問，通過重寫VisitCallExpr函數(shù)。函數(shù)定義除了進行還對函數(shù)中涉及到內(nèi)存訪問的表達式進行了代碼插樁，這里我們只介紹把main函數(shù)作為主線程進行多線程相關(guān)部分的插樁。

主函數(shù)的插樁算法是在主函數(shù)中進行無鎖哈希表的初始化工作。對于哈希表中的線程使用函數(shù)，直接生成memsafe.c和memsafe.h文件，這兩個文件包含了多線程C程序在進行內(nèi)存安全驗證時進行存儲的無鎖哈希表。

2.2 ? 多線程讀取哈希表

全局變量包含兩個哈希桶元素數(shù)組指針是因為我們需要創(chuàng)建兩個哈希表，一個存放函數(shù)元數(shù)據(jù)，一個存放指針元數(shù)據(jù)。哈希表是通過數(shù)組桶和無鎖鏈表組成的。由于每個線程需要有私有的pre，pcur，pnext去獨立的訪問哈希表，所以每個線程都獨自創(chuàng)建了私有的三個變量。我們在包裝線程創(chuàng)建函數(shù)時，創(chuàng)建每個線程對應(yīng)的私有值并記錄每個線程的線程ID。每個線程通過自己創(chuàng)建的3個MarkPtrType類型去獨立的訪問哈希表中存儲信息的無鎖鏈表，避免線程之間訪問時，對訪問變量的競爭。哈希表中存放了void **value變量。通過定義二級指針的方式用來存儲指針元數(shù)據(jù)和函數(shù)元數(shù)據(jù)，通過二級指針強制類型轉(zhuǎn)化的方式，將void**分別轉(zhuǎn)化為PREFIXpmd**和PREFIXfmd**。表1所示定義指針元數(shù)據(jù)和函數(shù)元數(shù)據(jù).

3 ? 實 ? 驗

3.1 ? 哈希表性能分析

本小節(jié)主要工作是對哈希表對于內(nèi)存安全的性能進行分析。第一部分在單線程的情況下將下面4種類型的哈希表進行數(shù)據(jù)對比。實驗數(shù)據(jù)如圖1所示。實驗數(shù)據(jù)是由十次結(jié)果的平均值來獲取的。其中A為使用數(shù)組和鏈表組成的哈希表，B為不支持并行操作的可擴展的哈希表;C為支持并發(fā)操作的哈希表，為A類型加入互斥操作而來;D為本文實現(xiàn)的哈希表。

圖1中縱坐標代表著單線程程序進行哈希表存取的運行時間。由此可以看出單線程情況下B哈希表的時間是A哈希表的4倍左右，D哈希表的時間是C可擴展哈希表的四倍左右。這是因為本文設(shè)計的哈希表D和可擴充的哈希表B是存儲在無鎖有序的鏈表之中。而一般的哈希表存儲時數(shù)組鏈接的鏈表只是用來處理哈希沖突的，鏈表不一定需要有序。該原因使得單線程情況下采用可擴展的哈希表結(jié)構(gòu)，性能有所降低。

第二部分，由于A哈希表和B哈希表沒有進行并行的設(shè)計所以無法進行多線程情況下，哈希表的存取操作。數(shù)據(jù)如圖2所示。

圖2中縱坐標的單位是微秒。代表著多線程程序運行的時間。本文所設(shè)計的可擴展哈希表D在線程數(shù)增加時，哈希表的時間沒有增加。而B哈希表的時間隨著線程數(shù)的增加而增加。這是應(yīng)為，B在哈希表進行擴展的時候，首先需要擴展哈希表容量，然后將原來哈希表中的值重新存儲到擴展之后的哈希表。在此期間，其它線程時無法進行哈希表存取的，從而導(dǎo)致B哈希表的性能因為線程的增加而變差。

3.2 ? 多線程C程序內(nèi)存安全的有效性實驗和性能

實驗

由于需要檢測C程序的內(nèi)存安全問題，所以我們需要對不同的內(nèi)存安全類型進行檢測。為此我們使用SARD（Software Assurance Reference Datase）作為多線程的C語言進行內(nèi)存安全的測試集。然后將本文的工具和SoftBoundCets[12-13]工具、Cruiser[14]工具進行比較。實驗結(jié)果如表2所示。SoftBC指SoftBoundCets，Cru指Cruiser。

表2 ? Movec、SoftBoundCets、Cruiser對比

表2中Yes表示能檢測出所有線程以及該線程存在的內(nèi)存安全錯誤，No表示不能檢測出所有線程的內(nèi)存安全錯誤。通過使用多個線程，并且每個線程運行不同的錯誤類型來比較工具對多線程、多內(nèi)存錯誤類型的有效性判定。由表可知SoftBoundCets僅支持單線程下內(nèi)存安全性問題的判定;Cruiser支持單線程和多線程關(guān)于堆內(nèi)存內(nèi)存安全的判定。而我們設(shè)計拓展的Movec工具可以支持單線程和多線程下多種內(nèi)存安全的判定。該表說明本文的工具在有效性上要比SoftBoundCets、Cruiser工具好。支持的范圍更廣。

另外本文使用該工具直接對SARD中的多線程C程序進行驗證實驗結(jié)果如表3所示。表中的數(shù)據(jù)代表著程序運行的時間，單位是微妙/us。

表3說明該工具可以有效的對開源測試集進行源代碼插樁，并正確的運行插樁之后的程序。

由于C語言主要的應(yīng)用領(lǐng)域是嵌入式平臺，而卻隨著嵌入式硬件系統(tǒng)的不斷升級，多線程的C程序在嵌入式平臺也變的越來越常見，所以本節(jié)剩余部分，通過嵌入式平臺的應(yīng)用程序?qū)ovec的性能進行分析。其中MiBench一共包括35個程序，分別由通信，網(wǎng)絡(luò)，安全，電子消費、工業(yè)制造和辦公自動化六個部分組成。每個應(yīng)用包含源文件、MakeFile文件和配置文件。通過選取其中的Dijkstra（small）、Dijkstra（large）、CRC32、basicmath（small）、basicmath（large）這三個部分進行實驗。實驗結(jié)果如表6所示，表中的時間單位為秒/s，代表著多線程程序運行的時間，表中的數(shù)據(jù)為10次運行之后，統(tǒng)計時間的平均值。

4 ? 結(jié) ? 論

介紹對多線程程序進行運行時驗證[15]的

原理，對于多核程序該如何處理各個事件序列。然后主要介紹對于無鎖哈希表設(shè)計模式和實現(xiàn)算法，其中哈希表中內(nèi)容主要存儲在無鎖的鏈表中，并介紹支持多線程操作的查詢，插入，刪除的無鎖鏈表，在此基礎(chǔ)上設(shè)計可擴展的哈希表。通過設(shè)計插樁算法和clang編譯器完成支持多線程程序的運行時驗證的工具Movec[16]。最后通過在多線程和單線程情況下分析哈希表的性能;將設(shè)計后的Movec與SoftBoundCets、Cruiser進行有效性的對比實驗得出本文設(shè)計的工具更適合對于多線程程序的內(nèi)存安全監(jiān)測;并使用開源測試集SARD和Mibench進

行性能分析實驗。接下來的工作主要是以下幾個方面：

（1）結(jié)合靜態(tài)分析技術(shù)，減少C程序中不必要的一些插樁

（2）在原有的數(shù)據(jù)結(jié)構(gòu)存儲結(jié)構(gòu)上進行優(yōu)化，提高數(shù)據(jù)查找的速度

（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] ?張碩，賀飛. 運行時驗證技術(shù)的研究進展[J].計算機科學(xué)，2014，41（ 11） ： 359—363.

[16] ?王哲民，陳哲，朱云龍，等. 參數(shù)化運行時驗證研究和工具實現(xiàn)[J]. 小型微型計算機系統(tǒng)，2016，37（12）：2667—2672.