陳韜 王明明

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

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

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

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

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

1.提出多線程程序的運(yùn)行時(shí)驗(yàn)證原理。

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

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

4.使用該工具和SoftBoundCets、Crusier工具進(jìn)行有效性對(duì)比實(shí)驗(yàn)，然后通過(guò)MiBench、SARD開(kāi)源測(cè)試集進(jìn)行性能實(shí)驗(yàn)。最后得出結(jié)論。

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

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

1.1 ? 無(wú)鎖有序鏈表

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

1.2 ? 可擴(kuò)充哈希表

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

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

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

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

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

實(shí)現(xiàn)

2.1 ? 插樁算法

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

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

2.2 ? 多線程讀取哈希表

全局變量包含兩個(gè)哈希桶元素?cái)?shù)組指針是因?yàn)槲覀冃枰獎(jiǎng)?chuàng)建兩個(gè)哈希表，一個(gè)存放函數(shù)元數(shù)據(jù)，一個(gè)存放指針元數(shù)據(jù)。哈希表是通過(guò)數(shù)組桶和無(wú)鎖鏈表組成的。由于每個(gè)線程需要有私有的pre，pcur，pnext去獨(dú)立的訪問(wèn)哈希表，所以每個(gè)線程都獨(dú)自創(chuàng)建了私有的三個(gè)變量。我們?cè)诎b線程創(chuàng)建函數(shù)時(shí)，創(chuàng)建每個(gè)線程對(duì)應(yīng)的私有值并記錄每個(gè)線程的線程ID。每個(gè)線程通過(guò)自己創(chuàng)建的3個(gè)MarkPtrType類(lèi)型去獨(dú)立的訪問(wèn)哈希表中存儲(chǔ)信息的無(wú)鎖鏈表，避免線程之間訪問(wèn)時(shí)，對(duì)訪問(wèn)變量的競(jìng)爭(zhēng)。哈希表中存放了void **value變量。通過(guò)定義二級(jí)指針的方式用來(lái)存儲(chǔ)指針元數(shù)據(jù)和函數(shù)元數(shù)據(jù)，通過(guò)二級(jí)指針強(qiáng)制類(lèi)型轉(zhuǎn)化的方式，將void**分別轉(zhuǎn)化為PREFIXpmd**和PREFIXfmd**。表1所示定義指針元數(shù)據(jù)和函數(shù)元數(shù)據(jù).

3 ? 實(shí) ? 驗(yàn)

3.1 ? 哈希表性能分析

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

圖1中縱坐標(biāo)代表著單線程程序進(jìn)行哈希表存取的運(yùn)行時(shí)間。由此可以看出單線程情況下B哈希表的時(shí)間是A哈希表的4倍左右，D哈希表的時(shí)間是C可擴(kuò)展哈希表的四倍左右。這是因?yàn)楸疚脑O(shè)計(jì)的哈希表D和可擴(kuò)充的哈希表B是存儲(chǔ)在無(wú)鎖有序的鏈表之中。而一般的哈希表存儲(chǔ)時(shí)數(shù)組鏈接的鏈表只是用來(lái)處理哈希沖突的，鏈表不一定需要有序。該原因使得單線程情況下采用可擴(kuò)展的哈希表結(jié)構(gòu)，性能有所降低。

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

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

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

實(shí)驗(yàn)

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

表2 ? Movec、SoftBoundCets、Cruiser對(duì)比

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

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

表3說(shuō)明該工具可以有效的對(duì)開(kāi)源測(cè)試集進(jìn)行源代碼插樁，并正確的運(yùn)行插樁之后的程序。

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

4 ? 結(jié) ? 論

介紹對(duì)多線程程序進(jìn)行運(yùn)行時(shí)驗(yàn)證[15]的

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

行性能分析實(shí)驗(yàn)。接下來(lái)的工作主要是以下幾個(gè)方面：

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

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

（3）將源代碼的插樁過(guò)程分配到不同的處理器核心上，提高M(jìn)ovec工具編譯運(yùn)行的性能。

參考文獻(xiàn)

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

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