吳亦澤 于佳耕 鄭 晨 武延軍,3

1 （中國(guó)科學(xué)院軟件研究所 北京 100190）

2 （中國(guó)科學(xué)院大學(xué) 北京 101408）

3 （計(jì)算機(jī)科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室（中國(guó)科學(xué)院軟件研究所）北京 100190）

應(yīng)用程序編程接口（application programming interface，API）是為其他軟件提供服務(wù)的軟件接口[1]，將計(jì)算機(jī)與軟件或軟件與軟件連接，為軟件開發(fā)者提供幫助.應(yīng)用軟件使用操作系統(tǒng)提供的功能時(shí)，需要調(diào)用操作系統(tǒng)提供的API.在Linux 各發(fā)行版中，為了讓應(yīng)用開發(fā)者能更方便地使用系統(tǒng)API 以實(shí)現(xiàn)更復(fù)雜的功能，系統(tǒng)將API 進(jìn)一步封裝至C 標(biāo)準(zhǔn)庫(kù)（本文簡(jiǎn)稱C 庫(kù)）中，并將C 庫(kù)的API 供用戶調(diào)用.C 庫(kù)連接了應(yīng)用軟件和操作系統(tǒng)，C 庫(kù)的接口實(shí)現(xiàn)影響應(yīng)用軟件對(duì)系統(tǒng)功能的使用.如果應(yīng)用軟件不能通過調(diào)用C庫(kù)接口來(lái)和系統(tǒng)建立聯(lián)系，很多關(guān)鍵的應(yīng)用功能也將無(wú)法實(shí)現(xiàn).

常見的GNU/Linux 類桌面和服務(wù)器系統(tǒng)都采用GNU C library（glibc）這套C 語(yǔ)言標(biāo)準(zhǔn)庫(kù)，它實(shí)現(xiàn)了多種多樣的C 庫(kù)接口，支持各類系統(tǒng)平臺(tái)，功能十分齊全.glibc 使用LGPL v2.1（GNU Lesser General Public License v2.1）協(xié)議.與GPL（GNU General Public License）協(xié)議要求“任何使用、修改和衍生GPL 庫(kù)的軟件必須采用GPL 協(xié)議并開源”不同的是，LGPL 允許軟件通過類庫(kù)引用的方式使用LGPL 庫(kù)而無(wú)需開源，但對(duì)于系統(tǒng)開發(fā)者而言，在對(duì)庫(kù)進(jìn)行修改或衍生時(shí)LGPL仍具有限制性和傳染性.因此，在商業(yè)化系統(tǒng)中使用glibc 存在強(qiáng)制開源的不便和安全問題.

為了避免系統(tǒng)搭載的C 庫(kù)因開源協(xié)議而在商業(yè)化場(chǎng)景下帶來(lái)問題，開源歐拉（openEuler）操作系統(tǒng)商業(yè)發(fā)行版的開發(fā)者正在考慮用musl libc 替換glibc.musl libc 是一個(gè)使用MIT 許可證的輕量級(jí)C 庫(kù)，MIT許可證在有版權(quán)聲明的條件下允許任意地使用、復(fù)制、修改和散布軟件而無(wú)需開源.musl libc 可用于從小型嵌入式系統(tǒng)到通用桌面、服務(wù)器系統(tǒng)的很多場(chǎng)景，具有體量小、魯棒性和安全性強(qiáng)、易于裝載等優(yōu)勢(shì).因其基礎(chǔ)架構(gòu)較為成熟，使用的協(xié)議也適用于商業(yè)場(chǎng)景，故musl libc 成為替換glibc 的首要選擇.

新C 庫(kù)對(duì)原有應(yīng)用軟件的兼容是C 庫(kù)替換工作的關(guān)鍵——新C 庫(kù)應(yīng)當(dāng)保證在原有C 庫(kù)下能正確運(yùn)行的應(yīng)用軟件在替換后也能正確運(yùn)行.目前，musl libc 相比glibc 有較多功能缺失，如果直接進(jìn)行替換，將導(dǎo)致C 庫(kù)對(duì)應(yīng)用軟件的兼容性較低，而低兼容性嚴(yán)重影響操作系統(tǒng)提供的服務(wù)質(zhì)量，降低商業(yè)系統(tǒng)的市場(chǎng)競(jìng)爭(zhēng)力.因此，在替換前需要通過補(bǔ)全開發(fā)將musl libc 的兼容性提高到足夠高的水平.

兼容性分析對(duì)新C 庫(kù)的開發(fā)很有幫助[2]，然而現(xiàn)有的兼容性分析方法并不適用于openEuler 對(duì)musl libc 的補(bǔ)全工作（見1.3 節(jié)和6.3 節(jié)）.針對(duì)這個(gè)問題，本文提出新的兼容性分析算法來(lái)研究openEuler 的4 種主要軟件生態(tài)中的musl libc 兼容性和缺失API 優(yōu)先級(jí).本文的研究目的是幫助openEuler 的C 庫(kù)開發(fā)者了解musl libc 在openEuler 操作系統(tǒng)上的兼容性，并參照優(yōu)先級(jí)順序補(bǔ)全開發(fā)接口，合理安排開發(fā)工作.

本文的主要貢獻(xiàn)有4 個(gè)方面：

1）量化對(duì)比了musl libc 與glibc 的接口.根據(jù)接口開發(fā)現(xiàn)狀，將全部接口劃分為主要接口和非主要接口，并分別進(jìn)行接口對(duì)比分析，量化了musl libc 和glibc 的接口差異和重合率，論證了對(duì)musl libc 進(jìn)行補(bǔ)全的必要性和可行性.

2）量化分析了musl libc 對(duì)應(yīng)用軟件生態(tài)的兼容情況.根據(jù)應(yīng)用軟件對(duì)缺失API 的調(diào)用情況和應(yīng)用之間的依賴關(guān)系提出了兼容的定義，將依賴關(guān)系構(gòu)建為圖模型，將兼容的定義形式化，并統(tǒng)計(jì)分析了應(yīng)用軟件生態(tài)的兼容情況.

3）提出了兼容性度量算法——PackageRank.PackageRank 在圖模型上為應(yīng)用軟件賦分，并通過計(jì)算兼容應(yīng)用的得分占比來(lái)度量兼容性.

4）提出了缺失API 優(yōu)先級(jí)算法——APIRank.APIRank 是PackageRank 的延伸，根據(jù)缺失API 被應(yīng)用軟件調(diào)用的情況，對(duì)圖模型作出進(jìn)一步擴(kuò)展，并在新的圖模型上為API 賦分，以度量缺失API 的優(yōu)先級(jí).

1 相關(guān)工作

1.1 C 標(biāo)準(zhǔn)庫(kù)

除glibc 和musl libc 外，還有多種其他C 標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)，如eglibc，uClibc，dietlibc 等.eglibc 是glibc 的一個(gè)分支，專為嵌入式場(chǎng)景設(shè)計(jì)，嚴(yán)格兼容二進(jìn)制的glibc，使用LGPL v2.1 協(xié)議，2014 年初停止開發(fā)；uClibc為嵌入式Linux 系統(tǒng)開發(fā)，其迎合小型C 庫(kù)需求，使用LGPL v2.1 協(xié)議，自2012 年5 月以來(lái)未有新發(fā)行版本；dietlibc 適用于小型場(chǎng)景，可以為多種體系結(jié)構(gòu)的Linux系統(tǒng)提供靜態(tài)鏈接二進(jìn)制庫(kù)，使用GPL v2 協(xié)議，最新版本于2018 年9 月發(fā)行，版本間隔為4～5 年.相較之下，musl libc 使用MIT 協(xié)議，版本更新周期為6～12個(gè)月，最新版本發(fā)布于2022 年4 月.

musl libc 官方發(fā)布了對(duì)自己C 庫(kù)的兼容性分析報(bào)告[3]，將musl libc（1.1.24）與多種C 語(yǔ)言標(biāo)準(zhǔn)和其他C 庫(kù)進(jìn)行了比較.分析顯示，musl libc 對(duì)POSIX 2008，C99，C11 標(biāo)準(zhǔn)的兼容性良好，分別有12 個(gè)、2 個(gè)、88個(gè)API 未實(shí)現(xiàn)，對(duì)比POSIX 2008 標(biāo)準(zhǔn)有2 個(gè)API 有函數(shù)原型但沒有實(shí)現(xiàn).在與glibc，uClibc，dietlibc 進(jìn)行對(duì)比時(shí)，musl libc 的魯棒性、安全性、構(gòu)建環(huán)境適配性均優(yōu)于其他C 庫(kù)；性能和體系結(jié)構(gòu)適配性略低于glibc 而遠(yuǎn)優(yōu)于uClibc 和dietlibc；體量略大于dietlibc，略小于uClibc，遠(yuǎn)小于glibc.此外，musl libc 在I/O、信號(hào)處理、正則表達(dá)式功能和動(dòng)態(tài)鏈接等方面與glibc存在功能性差異.

我們?cè)赨buntu 20.04 桌面版（Intel?Core? i7-8550U CPU @ 1.80GHz 2.00 GHz）上使用libc-bench-20110206[4]測(cè)試集分別對(duì)glibc（2.34）和musl libc（1.2.2）作了性能和內(nèi)存占有量的測(cè)試，測(cè)試結(jié)果展示在圖1中，其中測(cè)試用例和測(cè)試項(xiàng)目的含義見libc-bench[4].

Fig.1 Experimental results of performance and memory usage on glibc and musl libc圖1 glibc 與musl libc 的性能和內(nèi)存占有量實(shí)驗(yàn)結(jié)果

數(shù)據(jù)顯示，musl libc 在27 個(gè)測(cè)試中僅有3 個(gè)的性能比glibc 更高（運(yùn)行時(shí)間更短），而內(nèi)存占有量則有24 個(gè)更小（且基本都有明顯的優(yōu)勢(shì)）.這表明，雖然musl libc 的性能仍需提升，但其內(nèi)存占有量低，因此補(bǔ)全開發(fā)工作將更為方便和靈活.

綜合以上分析，musl libc 架構(gòu)成熟，許可協(xié)議對(duì)商用友好，適合進(jìn)行補(bǔ)全開發(fā)和C 庫(kù)替換.另一方面，性能較低、功能有差別和缺陷等問題使得直接替換并不可行，補(bǔ)全開發(fā)工作是必要的.

1.2 openEuler

openEuler 是一個(gè)開源、免費(fèi)的Linux 發(fā)行版平臺(tái)，它通過開放形式的社區(qū)與全球的開發(fā)者共同構(gòu)建一個(gè)開放、多元和架構(gòu)包容的軟件生態(tài)體系.2020年3 月，openEuler 社區(qū)正式發(fā)布了首個(gè)長(zhǎng)期支持版本——openEuler 20.03 LTS，并與多家操作系統(tǒng)廠商共同發(fā)布了基于openEuler 的商業(yè)系統(tǒng)發(fā)行版.openEuler每6 個(gè)月發(fā)布一個(gè)社區(qū)創(chuàng)新版本，提供6 個(gè)月社區(qū)支持，而LTS 版本的發(fā)布間隔周期為2 年，提供4 年社區(qū)支持.目前，openEuler 22.03 LTS 已經(jīng)發(fā)布，有多家國(guó)內(nèi)外機(jī)構(gòu)宣布將推出基于openEuler 22.03 LTS 的商業(yè)發(fā)行版.

1.3 兼容性研究

在兼容性度量方法中，一種簡(jiǎn)單而直接的方法是計(jì)數(shù)滿足兼容條件的API 個(gè)數(shù)[5-8].其算法比較容易實(shí)現(xiàn)，但缺乏準(zhǔn)確性，即只關(guān)注API 本身是否兼容，并未考慮真實(shí)場(chǎng)景的API 調(diào)用情況.

一些兼容性研究者已經(jīng)意識(shí)到應(yīng)當(dāng)在度量方法中引入應(yīng)用軟件對(duì)API 調(diào)用情況進(jìn)行考量，而單一內(nèi)核（unikernel）的出現(xiàn)也啟發(fā)了他們做出這樣的改變.單一內(nèi)核由應(yīng)用程序與其依賴的系統(tǒng)組件的最小集打包制成，具有單一地址空間，可以直接在管理程序（hypervisor）或硬件層面運(yùn)行[9].由于單一內(nèi)核是根據(jù)應(yīng)用需求搭建的最小集，它必須確保囊括的API 足夠兼容應(yīng)用.一種搭建思路是以現(xiàn)有通用系統(tǒng)的構(gòu)件為基礎(chǔ)進(jìn)一步開發(fā)，例如Rumprun[10]和OSv[11]是由BSD 模塊重組生成，Lupine Linux[12]則采用了Linux內(nèi)核的特殊配置和Kernel Mode Linux 補(bǔ)丁.另外還可以設(shè)計(jì)API 兼容層來(lái)增強(qiáng)自己系統(tǒng)的兼容性[13-14].這樣搭建的單一內(nèi)核仍在使用通用系統(tǒng)的API 標(biāo)準(zhǔn)，因此兼容性是其開發(fā)過程的關(guān)鍵，它們的兼容性度量也應(yīng)當(dāng)從API 調(diào)用的角度出發(fā).

文獻(xiàn)[2]以Ubuntu 15.04 為基準(zhǔn)，分析了其他一些Linux 類系統(tǒng)或構(gòu)件（系統(tǒng)調(diào)用、C 庫(kù)、文件系統(tǒng)等）的API 重要性（API importance）和加權(quán)完整性（weighted completeness）.文獻(xiàn)[2]的作者認(rèn)為“產(chǎn)生兼容性度量不準(zhǔn)確問題的根本原因是缺乏對(duì)系統(tǒng)API 在實(shí)際中被調(diào)用情況的數(shù)據(jù)統(tǒng)計(jì)和分析”.該文獻(xiàn)利用Ubuntu/Debian 的應(yīng)用軟件安裝次數(shù)統(tǒng)計(jì)，從概率角度度量其他系統(tǒng)或構(gòu)件的兼容性.該文提出2個(gè)度量概念：

1）API 重要性.一部操作系統(tǒng)上會(huì)安裝多個(gè)應(yīng)用軟件，這樣的一個(gè)“安裝集”是該文獻(xiàn)統(tǒng)計(jì)的基本單位.API 的重要性定義為“調(diào)用該API 的應(yīng)用被安裝的概率”.一個(gè)應(yīng)用軟件被安裝的概率是包含該應(yīng)用的安裝集個(gè)數(shù)（該應(yīng)用的安裝次數(shù)）與所有安裝集個(gè)數(shù)（即系統(tǒng)總安裝次數(shù)）的比值，將不同應(yīng)用軟件的安裝視為獨(dú)立事件，便可以通過將所有調(diào)用某個(gè)API 的應(yīng)用軟件的安裝概率相乘，來(lái)計(jì)算API 重要性.

2）加權(quán)完整性.加權(quán)完整性用于度量系統(tǒng)或構(gòu)件對(duì)應(yīng)用的兼容性.應(yīng)用軟件分為被支持的（supported）和不被支持的（unsupported），而加權(quán)完整性的定義為“安裝集中被支持應(yīng)用數(shù)量占該集中所有應(yīng)用數(shù)量的比值的數(shù)學(xué)期望”.仍將不同應(yīng)用軟件的安裝視為獨(dú)立事件，便能計(jì)算出加權(quán)完整性的估計(jì)值.

許多有待進(jìn)一步開發(fā)的系統(tǒng)構(gòu)件都有API 兼容性上的不足，但也有研究表明Linux API 提供的功能是溢出的.Quach 等人[15]認(rèn)為現(xiàn)代Linux 內(nèi)核中無(wú)用的二進(jìn)制內(nèi)容可能引發(fā)棧膨脹（stack bloating），而DeMarinis 等人[16]指出多余的API 為系統(tǒng)黑客留下了更大的攻擊面.這些研究也從另一個(gè)角度辯證地解讀了兼容性：兼容作用應(yīng)當(dāng)貼合應(yīng)用的需求，盲目地追求兼容可能帶來(lái)負(fù)面效果，提升API 兼容性的開發(fā)工作需要有的放矢.

本文采用靜態(tài)分析度量兼容性，此外還可以采用動(dòng)態(tài)分析或靜態(tài)和動(dòng)態(tài)分析結(jié)合的方法.文獻(xiàn)[2]也采用了靜態(tài)分析度量系統(tǒng)和構(gòu)件的兼容性，Cui 等人[17]利用動(dòng)態(tài)二進(jìn)制翻譯（dynamic binary translation）技術(shù)分析了Intel SGX Enclaves 的系統(tǒng)調(diào)用的兼容性，Atlidakis 等人[18]將靜態(tài)和動(dòng)態(tài)結(jié)合來(lái)分析POSIX標(biāo)準(zhǔn)是否仍符合現(xiàn)代應(yīng)用的需求.鄭煒等人[19]總結(jié)了近年來(lái)安卓移動(dòng)應(yīng)用兼容性的靜態(tài)和動(dòng)態(tài)分析方法.動(dòng)態(tài)分析收集程序的運(yùn)行時(shí)數(shù)據(jù)，比靜態(tài)分析更加接近實(shí)際場(chǎng)景，但往往又無(wú)法準(zhǔn)確模擬程序?qū)嶋H工作時(shí)的行為.在兼容性研究中，測(cè)試用例的選取不當(dāng)會(huì)導(dǎo)致兼容問題不能在測(cè)試中暴露，降低兼容性分析的準(zhǔn)確性.

2 musl libc 與glibc 的接口對(duì)比

本節(jié)將進(jìn)行musl libc 與glibc 的接口對(duì)比分析.本節(jié)的結(jié)果是本文后續(xù)內(nèi)容的基礎(chǔ)和依據(jù).

在本文的研究中，musl libc 和glibc 均由官方倉(cāng)庫(kù)源碼編譯并安裝，見表1.編譯C 庫(kù)時(shí)使用的編譯器是x86_64-linux-gnu-gcc 9.4.0，安裝C 庫(kù)的系統(tǒng)是Ubuntu 20.04 桌面版.

Table 1 Versions and Repository Addresses of C Libraries表1 C 庫(kù)的版本號(hào)與倉(cāng)庫(kù)地址

2.1 接口名稱提取

鏈接器在鏈接時(shí)需要知道庫(kù)文件內(nèi)部定義了哪些接口，這要求被鏈接接口的信息必須完整保存在庫(kù)文件的符號(hào)表中.因此，可以從庫(kù)文件的符號(hào)表內(nèi)提取接口名稱.

本文研究中的接口名稱提取自C 庫(kù)中的可執(zhí)行文件（executable and linkable format，ELF）.具體方法為：遍歷C 庫(kù)所在目錄中的所有文件，讀取其中每個(gè)ELF的符號(hào)表.對(duì)于每個(gè)符號(hào)表項(xiàng)，如果其類型（type）為FUNC 或IFUNC 且可見度（bind）為GLOBAL 或 WEAK，則提取其符號(hào)名（name）.這樣提取的接口名稱僅包含可被鏈接的接口，而不可鏈接的接口與C 庫(kù)的兼容無(wú)關(guān)（僅定義在內(nèi)部，不能被應(yīng)用軟件調(diào)用），故不在本文的研究范圍內(nèi).

經(jīng)過提取，glibc 共有6 466 個(gè)接口，musl libc 共有1 898 個(gè).

2.2 主要接口

C 庫(kù)的接口有這樣的命名習(xí)慣：以字母起始的接口供用戶調(diào)用，以下劃線起始的接口實(shí)現(xiàn)內(nèi)部和底層的功能（與操作系統(tǒng)交互、初始化和退出、編譯優(yōu)化等）.例如，printf 是標(biāo)準(zhǔn)輸出的常用接口，而__libc_start_main 是C 程序初始化啟動(dòng)的一部分，gcc 在編譯時(shí)可能會(huì)將printf 替換為_printf_chk 以防止棧溢出[2].本文將名稱以字母起始的接口稱為主要接口.

應(yīng)用軟件開發(fā)者應(yīng)該避免直接調(diào)用非主要接口[20]，故C 庫(kù)的底層差異不會(huì)導(dǎo)致兼容問題.然而，在靜態(tài)分析應(yīng)用軟件對(duì)接口的調(diào)用情況時(shí)，非主要接口可能會(huì)帶來(lái)兼容性的誤判.例如，應(yīng)用軟件調(diào)用的printf在gcc 編譯時(shí)被替換為_printf_chk，由于musl libc 未實(shí)現(xiàn)_printf_chk，所以分析結(jié)果將顯示該應(yīng)用軟件調(diào)用了未實(shí)現(xiàn)的接口，從而存在兼容問題.但是，如果使用musl-gcc 編譯，程序可以正確鏈接musl libc 的printf 接口，所以兼容問題實(shí)際上并不存在.

雖然本文的研究角度是二進(jìn)制兼容，但這樣的誤判將導(dǎo)致兼容性分析結(jié)果不準(zhǔn)確，這是我們希望避免的.因此，本文在兼容性度量時(shí)只對(duì)主要接口做統(tǒng)計(jì)和分析.除特別注明外，后文中所述的結(jié)果均以主要接口為研究對(duì)象.

經(jīng)篩選，glibc 有2 883 個(gè)主要接口，musl libc 有1 516 個(gè).

2.3 接口對(duì)比分析

全部接口和主要接口的統(tǒng)計(jì)結(jié)果見表2.除接口數(shù)量外，為比較C 庫(kù)的接口實(shí)現(xiàn)相似度，表2 還統(tǒng)計(jì)了接口重合率，即C 庫(kù)的共同接口數(shù)與該C 庫(kù)在該項(xiàng)的總接口數(shù)的比值.

Table 2 APIs Comparison of musl libc and glibc表2 musl libc 和glibc 的接口對(duì)比

結(jié)果顯示，2 個(gè)C 庫(kù)的主要接口重合率均遠(yuǎn)高于各自的非主要接口重合率（glibc：52.2%和5.6%；musl libc：99.2%和52.1%）.這表明C 庫(kù)頂層接口的相似度較高，而底層實(shí)現(xiàn)區(qū)別較大.此外，glibc 中55%（3 583/6 466）的接口為非主要接口，可見其底層實(shí)現(xiàn)十分復(fù)雜，大量的非主要接口將嚴(yán)重影響接口對(duì)比結(jié)果的準(zhǔn)確性，對(duì)后續(xù)的分析也不利，而只分析主要接口便能避免這個(gè)問題.

musl libc 的主要接口集幾乎完全包含在glibc 的主要接口集中（重合率為99.2%）.因此，從主要接口的角度來(lái)看，musl libc 可以基本被視為glibc 的子集.這表明musl libc 充分遵從了glibc 的接口命名習(xí)慣，為open-Euler 的C 庫(kù)移植和替代工作帶來(lái)了很大便利.但同時(shí)，musl libc 的主要接口僅覆蓋glibc 主要接口的一半左右（52.2%），這也勢(shì)必降低了musl libc 對(duì)應(yīng)用軟件的兼容性.

表3 列出的12 個(gè)主要接口是musl libc 獨(dú)有的.我們?cè)诮y(tǒng)計(jì)應(yīng)用軟件調(diào)用接口的情況（具體方法見第3 節(jié)）后發(fā)現(xiàn)，這12 個(gè)接口均未被任何應(yīng)用軟件調(diào)用.值得一提的是，接口strlcat 和strlcpy 其實(shí)在應(yīng)用軟件中十分常見，雖然glibc 并未實(shí)現(xiàn)這2 個(gè)接口，但應(yīng)用開發(fā)者仍會(huì)想辦法使用它們：有些開發(fā)者將它們實(shí)現(xiàn)在自己的鏈接庫(kù)中（例如x86_64 的multipathtools-0.8.5-7，strlcpy），有些靜態(tài)鏈接了他們自己編寫的函數(shù)（例如aarch64 的entr-4.5-1，strlcpy）.也正因如此，這些應(yīng)用軟件才能夠在glibc 下正確調(diào)用這2 個(gè)接口.

Table 3 Main APIs Owned by musl libc表3 musl libc 獨(dú)有的主要接口

musl libc 相比glibc 有1 379 個(gè)主要接口尚未實(shí)現(xiàn)，但它們的情況與musl libc 獨(dú)有的12 個(gè)接口截然不同.由于glibc 的廣泛使用，應(yīng)用軟件開發(fā)者一般都遵循glibc 的規(guī)范而進(jìn)行相應(yīng)的編程適配.如果開發(fā)者認(rèn)為glibc 已經(jīng)實(shí)現(xiàn)了某個(gè)接口，他們大多會(huì)選擇直接調(diào)用它而不會(huì)再自行實(shí)現(xiàn)該接口，因?yàn)榉菢?biāo)準(zhǔn)實(shí)現(xiàn)不僅帶來(lái)了更大的工作量，而且存在安全性隱患，也不利于代碼復(fù)用和移植.然而，開發(fā)者想要調(diào)用的接口可能是musl libc 未實(shí)現(xiàn)的，這便引發(fā)了musl libc 的兼容性問題.

“接口重合率”是度量兼容性的一種思路.如果將其用于本文的研究，能得到結(jié)論：musl libc 的兼容性是52.2%.然而，這種思路并未考慮被兼容的應(yīng)用軟件所包含的信息.C 庫(kù)通過實(shí)現(xiàn)接口來(lái)為應(yīng)用軟件提供功能支持，而應(yīng)用軟件通過調(diào)用接口來(lái)滿足自身的功能需求.在兼容的過程中，主體是C 庫(kù)，客體是應(yīng)用軟件，而用接口重合率來(lái)度量兼容性的方法僅考慮了主體，而忽略了客體.由此可見，應(yīng)用軟件對(duì)C 庫(kù)接口的調(diào)用情況也應(yīng)當(dāng)被納入兼容性的度量中.我們將在第4～5 節(jié)中提出了相應(yīng)的算法，更加全面而準(zhǔn)確地度量兼容性，并進(jìn)一步度量了每個(gè)缺失API 的優(yōu)先級(jí).

3 應(yīng)用軟件生態(tài)兼容分析

應(yīng)用軟件生態(tài)是指系統(tǒng)上可運(yùn)行的所有應(yīng)用軟件的集合，本文中簡(jiǎn)稱為軟件生態(tài)或生態(tài).不同系統(tǒng)的應(yīng)用軟件生態(tài)不同，故C 庫(kù)的兼容情況也有區(qū)別.本文研究musl libc 在openEuler 操作系統(tǒng)的4 種軟件生態(tài)中的兼容性，軟件生態(tài)分別為aarch64 服務(wù)器、x86_64 服務(wù)器、aarch64 嵌入式和x86_64 嵌入式.

openEuler 軟件生態(tài)中的應(yīng)用軟件均可通過RPM（RedHat package manager）格式的軟件包安裝.RPM 包中含有應(yīng)用軟件安裝所需的文件和信息，包括ELF、文檔、協(xié)議等.為提高結(jié)果的準(zhǔn)確性，本文所統(tǒng)計(jì)和分析的應(yīng)用軟件生態(tài)均排除了glibc 和musl libc 的基本包與擴(kuò)展包，如表4 所示.

Table 4 Basic Package and Extended Package of C Libraries表4 C 庫(kù)的基本包與擴(kuò)展包

本節(jié)將介紹C 庫(kù)兼容應(yīng)用軟件的定義，并依照此定義分析4 種生態(tài)中的應(yīng)用軟件兼容情況.

3.1 直接兼容的定義

兼容的直觀判定標(biāo)準(zhǔn)是，新C 庫(kù)能否保證應(yīng)用軟件的全部可執(zhí)行文件正確運(yùn)行.C 庫(kù)無(wú)法支持可執(zhí)行文件正確運(yùn)行的原因有很多，被調(diào)用的接口未實(shí)現(xiàn)、實(shí)現(xiàn)的功能有缺陷或錯(cuò)誤、應(yīng)用開發(fā)者編程錯(cuò)誤、鏈接器有漏洞等都是可能的原因.本文只考慮C庫(kù)未實(shí)現(xiàn)需要調(diào)用的接口的情況，即只要C 庫(kù)實(shí)現(xiàn)了應(yīng)用軟件調(diào)用的接口，就認(rèn)為該調(diào)用不會(huì)發(fā)生錯(cuò)誤.另一方面，如果C 庫(kù)未實(shí)現(xiàn)需要調(diào)用的接口，本文也假設(shè)應(yīng)用軟件開發(fā)者未在別處（如自行開發(fā)的鏈接庫(kù)中）實(shí)現(xiàn)這些接口（2.3 節(jié)中解釋了這樣假設(shè)的合理性）.

既然C 庫(kù)接口不會(huì)被自行實(shí)現(xiàn)，那么應(yīng)用軟件調(diào)用的庫(kù)接口便完全依賴C 庫(kù)提供.因此，如果C 庫(kù)要保證應(yīng)用軟件不出現(xiàn)錯(cuò)誤，就必須實(shí)現(xiàn)應(yīng)用軟件調(diào)用的全部接口.這種“保證”是C 庫(kù)對(duì)應(yīng)用軟件的直接支持，本文將其稱為直接兼容.

定義1.C 庫(kù)直接不兼容應(yīng)用軟件.如果在該應(yīng)用軟件的RPM 包中存在某個(gè)ELF，該ELF 調(diào)用了C庫(kù)缺失的接口，則C 庫(kù)直接不兼容該應(yīng)用軟件.如果不滿足上述條件，則C 庫(kù)直接兼容該應(yīng)用軟件.

上述的接口“調(diào)用”指的是靜態(tài)調(diào)用，即ELF 的符號(hào)表中存在能夠動(dòng)態(tài)鏈接該接口的條目.提取符號(hào)表中動(dòng)態(tài)鏈接項(xiàng)的符號(hào)名，便提取出了所調(diào)用接口的名稱.

然而，即使“調(diào)用”了C 庫(kù)缺失的接口，ELF 運(yùn)行時(shí)也未必會(huì)發(fā)生錯(cuò)誤，因?yàn)閳?zhí)行流可能并不會(huì)經(jīng)過這個(gè)接口.例如，某個(gè)負(fù)責(zé)崩潰處理功能的接口在符號(hào)表中有相應(yīng)的項(xiàng)，但若程序未遇到崩潰，便不會(huì)真正調(diào)用它.因此，即使存在對(duì)缺失接口的“調(diào)用”，應(yīng)用軟件在運(yùn)行時(shí)也未必出現(xiàn)錯(cuò)誤.

本文不考慮動(dòng)態(tài)調(diào)用引起的偏差，即應(yīng)用軟件對(duì)任何C 庫(kù)缺失接口的靜態(tài)調(diào)用都會(huì)被判定為直接不兼容.事實(shí)上，可以充分信任應(yīng)用軟件開發(fā)者的編程能力，從而相信這些極少或從未被真正調(diào)用過的接口并非冗余，而是開發(fā)者希望該應(yīng)用實(shí)現(xiàn)的功能（如崩潰處理功能）的一部分，它們的缺失也會(huì)使應(yīng)用的正確運(yùn)行不再得到保證.

3.2 不兼容的傳遞性

RPM 包中還記錄著應(yīng)用軟件對(duì)其他應(yīng)用軟件的依賴關(guān)系，這種顯式的依賴關(guān)系是功能上的依賴.除此之外，應(yīng)用之間還存在隱性的依賴關(guān)系，例如用戶在使用一個(gè)后端應(yīng)用時(shí)必須搭配某個(gè)前端應(yīng)用才能獲得良好體驗(yàn).本文只考慮RPM 包中顯式標(biāo)注的依賴關(guān)系，不考慮其他隱性依賴關(guān)系.

應(yīng)用軟件的兼容與否和它所依賴的其他應(yīng)用軟件有關(guān).對(duì)于某個(gè)應(yīng)用軟件，即使它所依賴的應(yīng)用軟件使用C 庫(kù)時(shí)都能正確運(yùn)行，它也未必能正確運(yùn)行，故“應(yīng)用是否被兼容”和“所依賴應(yīng)用是否被兼容”沒有直接關(guān)系.但反之，如果所依賴的應(yīng)用不能正確運(yùn)行，應(yīng)用軟件本身的正確運(yùn)行便也無(wú)法得到保證，則是一個(gè)因果關(guān)系.

因此，不兼容具有傳遞性，即C 庫(kù)如果不兼容某個(gè)應(yīng)用軟件，則也不兼容依賴該應(yīng)用軟件的其他應(yīng)用軟件，即使這些應(yīng)用軟件自身是被直接兼容的.圖2 是一個(gè)例子：A，B，C，D這4 個(gè)應(yīng)用中，C依賴A，D依賴A和B，E依賴C和D，箭頭表示依賴關(guān)系.庫(kù)直接兼容應(yīng)用A，C，D，E，直接不兼容B.雖然D被直接兼容，但因?yàn)锽是直接不兼容的，而D依賴B，所以B的不兼容傳遞到D，D也不被兼容.同理，D再將不兼容性傳遞到E，E也不被兼容.

Fig.2 Illustration of transitivity of incompatibility圖2 不兼容的傳遞性示意圖

3.3 兼容的定義

從3.1 節(jié)的直接兼容和3.2 節(jié)中的不兼容傳遞性出發(fā)，可以對(duì)C 庫(kù)兼容應(yīng)用軟件做出定義.

定義2.C 庫(kù)是否兼容應(yīng)用軟件.

1）如果C 庫(kù)直接不兼容一個(gè)應(yīng)用軟件，則C 庫(kù)不兼容該應(yīng)用軟件.

2）如果C 庫(kù)不兼容一個(gè)應(yīng)用軟件所依賴的某個(gè)應(yīng)用軟件，則C 庫(kù)不兼容該應(yīng)用軟件.

3）如果無(wú)法通過以上2 條定義證明C 庫(kù)不兼容一個(gè)應(yīng)用軟件，則C 庫(kù)兼容該應(yīng)用軟件.

定義2是遞歸的.首先有一些應(yīng)用是直接不兼容的，從而依賴它們的應(yīng)用是不兼容的.不兼容性沿著依賴關(guān)系網(wǎng)傳遞，直至所有不兼容的應(yīng)用都被傳遞到，而未被傳遞到的應(yīng)用就是兼容的.

定義2也是無(wú)歧義的.該定義將應(yīng)用軟件嚴(yán)格分為兼容的和不兼容的，不存在一個(gè)應(yīng)用可以同時(shí)被判定為兼容和不兼容的情況.這是非常重要的，因?yàn)槟：亩x將從根本上降低兼容性分析結(jié)果的準(zhǔn)確性.

3.4 軟件生態(tài)圖

定義2是自然語(yǔ)言表述的兼容定義，不利于直接用于判定應(yīng)用軟件是否兼容.數(shù)學(xué)化的模型在判定時(shí)將更為有效.

應(yīng)用軟件之間的依賴關(guān)系存在方向性.由此，可以將整個(gè)軟件生態(tài)視為一張有向圖，應(yīng)用軟件與圖中的點(diǎn)一一對(duì)應(yīng)，而依賴關(guān)系與圖中的有向邊也一一對(duì)應(yīng).我們把這樣的圖模型稱為軟件生態(tài)圖.

定義3.軟件生態(tài)圖.它是一張表示軟件生態(tài)中的應(yīng)用軟件及其之間依賴關(guān)系的有向圖.圖中的每個(gè)點(diǎn)對(duì)應(yīng)生態(tài)中的一個(gè)應(yīng)用軟件，每條邊對(duì)應(yīng)一個(gè)依賴關(guān)系，邊的方向規(guī)定為：應(yīng)用A依賴應(yīng)用B，對(duì)應(yīng)從A指向B的邊.

在軟件生態(tài)圖中，我們把被兼容的應(yīng)用稱為兼容點(diǎn)，不被兼容的應(yīng)用稱為不兼容點(diǎn)，同理也有直接兼容點(diǎn)和直接不兼容點(diǎn).我們提出定義2 在軟件生態(tài)圖模型下的一個(gè)等價(jià)定義，并證明其等價(jià)性.

定義4.軟件生態(tài)圖中的不兼容點(diǎn).它是那些可通過圖中的路徑到達(dá)直接不兼容點(diǎn)的結(jié)點(diǎn)（路徑長(zhǎng)度可以為0），即

其中Sdi是直接不兼容（directly incompatible）的結(jié)點(diǎn)集，(v,vn,vn1,…,v1,v0)表示從v經(jīng)過vn,vn-1，…，v1到v0的路徑.

定義4與定義2 的等價(jià)性證明為：

1）對(duì)于可通過一條路徑到達(dá)直接不兼容點(diǎn)的點(diǎn)，如果這條路徑長(zhǎng)度為0，則該點(diǎn)是直接不兼容點(diǎn)，當(dāng)然也是不兼容點(diǎn)；否則，可以將該點(diǎn)記為a，路徑記為（a,an,an-1, …,a1,a0），n≥0，a0是直接不兼容點(diǎn).根據(jù)定義2，a0是不兼容點(diǎn)，a1因?yàn)橐蕾嚵瞬患嫒蔹c(diǎn)a0，也是不兼容點(diǎn).反復(fù)進(jìn)行推理可知，a1, …,an-1,an,a都是不兼容點(diǎn).

2）對(duì)于一個(gè)不兼容點(diǎn)b，現(xiàn)在要找到一條從它到某個(gè)不兼容點(diǎn)的路徑.根據(jù)定義2 第3 條，一定存在證明b是不兼容點(diǎn)的方法.也就是說(shuō)，通過某種方法運(yùn)用定義2 的第1 條和第2 條，最終可以推導(dǎo)出b不兼容.如果運(yùn)用了定義2 的第1 條，即b是直接不兼容點(diǎn)，則長(zhǎng)度為0 的路徑即為所求；否則，它依賴另一個(gè)不兼容點(diǎn)（第2 條），即存在從它到另一個(gè)不兼容點(diǎn)b0的邊.如果b0是直接不兼容點(diǎn)，則證明完成；否則，又存在b0到另一個(gè)不兼容點(diǎn)b1的邊.反復(fù)進(jìn)行這樣的推理，如果一直沒有訪問直接不兼容點(diǎn)，將不斷訪問b,b0,b1, …點(diǎn)序列，點(diǎn)序列與推理過程是一一對(duì)應(yīng)的.也就是說(shuō)，既然存在b是不兼容點(diǎn)的證明方法，就存在相應(yīng)的點(diǎn)序列.可以認(rèn)為證明方法對(duì)應(yīng)的點(diǎn)序列是無(wú)重復(fù)的（序列中每個(gè)點(diǎn)都是不同的），因?yàn)槌霈F(xiàn)重復(fù)點(diǎn)意味著推理過程遍歷了一個(gè)環(huán)，而這又意味著循環(huán)論證.循環(huán)論證本身不能作為證明方法，故最終還是需要從某個(gè)點(diǎn)跳出這個(gè)環(huán)才能完成證明，故不妨第一次訪問“跳出點(diǎn)”時(shí)就跳出，訪問過程便沒有了環(huán).又由于圖中點(diǎn)的個(gè)數(shù)有限，故無(wú)重復(fù)的點(diǎn)序列只能是有限長(zhǎng)度的，因而可以把證明方法對(duì)應(yīng)的點(diǎn)序列記作b,b0,b1, …,bn,n≥0.這表明，整個(gè)推理過程只會(huì)重復(fù)有限次便停止在bn，而推理停止的唯一原因?yàn)閎n是直接不兼容點(diǎn).（b,b0,b1, …,bn）就是所求路徑.

根據(jù)定義4，只要遍歷某個(gè)應(yīng)用結(jié)點(diǎn)的所有無(wú)環(huán)路徑，就可以判定該應(yīng)用是否被兼容.

3.5 應(yīng)用軟件生態(tài)兼容分析結(jié)果

表5 展示了openEuler 的4 種軟件生態(tài)的musl libc 兼容情況，其中第n級(jí)不兼容數(shù)的含義為在第n輪傳遞后新增加的不兼容應(yīng)用個(gè)數(shù)，兼容率為被兼容的應(yīng)用個(gè)數(shù)占全部應(yīng)用個(gè)數(shù)的比例.

Table 5 Statistics of Compatible Applications in the Four Ecosystems表5 4 種生態(tài)中的兼容的應(yīng)用軟件統(tǒng)計(jì)

比較表5 中數(shù)據(jù)發(fā)現(xiàn)，C 庫(kù)在相同應(yīng)用場(chǎng)景（服務(wù)器或嵌入式）、不同體系結(jié)構(gòu)下有著相近的直接兼容率和不兼容傳遞模式，而在相同體系結(jié)構(gòu)、不同應(yīng)用場(chǎng)景下數(shù)據(jù)的差異很大：服務(wù)器場(chǎng)景中兼容率分別為31.89%和31.87%，其各級(jí)不兼容傳遞的應(yīng)用個(gè)數(shù)分別為537/547，6 936/6 985，4 721/4 727，198/190，7/10；嵌入式場(chǎng)景中兼容率分別為45.24%和44.58%，其各級(jí)不兼容傳遞的應(yīng)用個(gè)數(shù)分別為33/33，13/13.而在不同應(yīng)用場(chǎng)景下，兼容率的差值分別為13.35%（aarch64）和12.71%（x86_64），不兼容傳遞模式也有明顯區(qū)別.

這表明，軟件生態(tài)兼容情況受應(yīng)用場(chǎng)景的影響很明顯，而受硬件體系結(jié)構(gòu)的影響很微弱.

4 兼容性算法

兼容性的度量是許多系統(tǒng)開發(fā)者的需求，而好的度量方法是獲得優(yōu)質(zhì)度量結(jié)果的關(guān)鍵所在.

3.5 節(jié)中提到的兼容率是一種樸素的度量方法，它基于一個(gè)簡(jiǎn)單的數(shù)學(xué)原理——計(jì)數(shù).每個(gè)應(yīng)用軟件都在計(jì)數(shù)時(shí)被同等地視作“1”，兼容應(yīng)用的個(gè)數(shù)和所有應(yīng)用的個(gè)數(shù)的比值就是度量結(jié)果.因此，兼容率不能體現(xiàn)不同應(yīng)用軟件之間的差別.

應(yīng)用軟件在生態(tài)中的重要性并不等同，這種差異體現(xiàn)在：

1）系統(tǒng)用戶的角度.生態(tài)中的一些應(yīng)用提供的功能十分基礎(chǔ)，很多其他應(yīng)用都依賴有基礎(chǔ)功能的應(yīng)用，這些“基礎(chǔ)應(yīng)用”往往存在于不同用戶所使用的應(yīng)用軟件的交集中.例如，所有的Python 擴(kuò)展包都需要Python 解釋器來(lái)運(yùn)行，故Python 解釋器便時(shí)常存在于交集中.用戶樂于身處能滿足他們個(gè)性化需求的軟件生態(tài)中，而這源于基礎(chǔ)應(yīng)用對(duì)生態(tài)中其他應(yīng)用的廣泛支持.對(duì)整個(gè)用戶群體而言，基礎(chǔ)應(yīng)用正常工作時(shí)的收益和崩潰時(shí)的損失都比其他應(yīng)用更大，這便是應(yīng)用重要性差異的體現(xiàn).

2）應(yīng)用軟件開發(fā)者的角度.應(yīng)用軟件開發(fā)者大多選擇以那些已經(jīng)廣泛支持其他應(yīng)用的應(yīng)用為基礎(chǔ)，開發(fā)自己的應(yīng)用軟件，因?yàn)榛A(chǔ)應(yīng)用的功能豐富，正確性和安全性得到廣泛的實(shí)踐驗(yàn)證，一般能得到持續(xù)穩(wěn)定的維護(hù)，從而使得開發(fā)工作更加便捷、產(chǎn)品穩(wěn)定性更佳、產(chǎn)品便于和其他應(yīng)用互通或適配，等等.這些優(yōu)勢(shì)使得開發(fā)者的產(chǎn)品更受用戶青睞，而這又促使更多開發(fā)者在這些基礎(chǔ)應(yīng)用之上開展工作，形成以基礎(chǔ)應(yīng)用為中心、其他應(yīng)用對(duì)其依賴的生態(tài)結(jié)構(gòu)，這是應(yīng)用重要性差異的又一體現(xiàn).

本節(jié)基于3.4 節(jié)中的軟件生態(tài)圖模型，提出了利用PackageRank 算法計(jì)算應(yīng)用軟件的重要性和C 庫(kù)的兼容性，以在兼容性度量時(shí)體現(xiàn)重要性差異.

4.1 影響應(yīng)用軟件重要性的因素

應(yīng)用軟件之間的依賴關(guān)系能反映其重要性差異.不論是從系統(tǒng)用戶還是應(yīng)用軟件開發(fā)者的角度，依賴關(guān)系都和應(yīng)用軟件重要性有著緊密的聯(lián)系.

被大量應(yīng)用軟件依賴的應(yīng)用軟件相對(duì)更加重要.然而，把被依賴次數(shù)當(dāng)作應(yīng)用軟件的重要性也有失偏頗，如某個(gè)“只被一個(gè)很重要的應(yīng)用依賴”的應(yīng)用可能比“被多個(gè)很不重要的應(yīng)用依賴”的應(yīng)用更重要，因?yàn)樗玛P(guān)生態(tài)中的重要應(yīng)用軟件的正常運(yùn)行.

綜上所述，應(yīng)用軟件的重要性受2 種因素影響：

1）被其他應(yīng)用依賴的次數(shù)；

2）依賴它的應(yīng)用的重要性.

4.2 PackageRank 算法

PackageRank 算法是本文提出的兼容性度量算法.該算法分為2 個(gè)部分：計(jì)算應(yīng)用軟件的重要性、計(jì)算C 庫(kù)的兼容性.

4.2.1 計(jì)算應(yīng)用軟件的重要性

PackageRank 算法同時(shí)考慮了4.1 節(jié)所述的影響應(yīng)用軟件重要性的2 種因素.它的思想基于Page 等人[21]提出的PageRank 算法，即PageRank 算法應(yīng)用于代表互聯(lián)網(wǎng)的有向圖中，而PackageRank 算法則是將其應(yīng)用到軟件生態(tài)圖.

圖3 展示了經(jīng)過簡(jiǎn)化的PackageRank 算法，它是一個(gè)迭代過程：每個(gè)結(jié)點(diǎn)將它現(xiàn)有的得分沿所有“出邊”平均分發(fā)，并將所有“入邊”的得分求和，作為新一輪迭代之前的得分.本文將PackageRank 算法經(jīng)過多次迭代得到的穩(wěn)定結(jié)果作為應(yīng)用軟件的重要性度量值.

Fig.3 Illustration of PackageRank algorithm圖3 PackageRank 算法示意圖

Package Rank 算法的含義是：

1）“入邊得分求和”使得被更多應(yīng)用依賴的應(yīng)用因?yàn)橛懈嗟梅謥?lái)源而獲得更高得分；

2）“出邊平均分發(fā)”使得被更高得分的應(yīng)用依賴的應(yīng)用能獲得更高得分.

由此可見，PackageRank 算法兼顧了影響應(yīng)用軟件重要性的2 個(gè)因素.

簡(jiǎn)化的PackageRank 存在2 個(gè)問題，Page 等人[21]將它們分別稱為排序沉沒（rank sink）和懸鏈接（dangling link），本文也采用這2 個(gè)稱呼.

1）排序沉沒.軟件生態(tài)圖中可能存在環(huán)，即應(yīng)用之間可以環(huán)形依賴.當(dāng)環(huán)中的全部應(yīng)用都被兼容時(shí)，它們都能正確運(yùn)行，否則便都不能正確運(yùn)行.如果存在指向環(huán)中某個(gè)點(diǎn)的邊，所有的點(diǎn)又均沒有指向環(huán)外其他點(diǎn)的邊，則得分可以進(jìn)入環(huán)但不能排出，從而在環(huán)中無(wú)限積累，如圖4 所示.可能存在1 個(gè)或多個(gè)這樣的環(huán)，而不在這些環(huán)內(nèi)的點(diǎn)最終都將沒有得分.

Fig.4 Illustration of rank sink圖4 排序沉沒示意圖

2）懸鏈接.有些應(yīng)用不依賴任何其他應(yīng)用，即它對(duì)應(yīng)的點(diǎn)在軟件生態(tài)圖中沒有出邊.在迭代過程中，賦予這些點(diǎn)的分?jǐn)?shù)將從圖中泄漏，如圖5 所示.

為了解決排序沉沒和懸鏈接，算法在每次迭代后令每個(gè)結(jié)點(diǎn)都“流失”一定比例的得分，同時(shí)向所有結(jié)點(diǎn)補(bǔ)充分配分?jǐn)?shù)以維持總得分恒定.其中，得分流失和補(bǔ)充使得所有得分不會(huì)全部流入閉環(huán)中，而得分補(bǔ)充還可以補(bǔ)足因懸鏈接而泄漏的得分.

考慮到上述問題和解決方法，我們把由Package-Rank 計(jì)算的應(yīng)用軟件重要性定義.

定義5.應(yīng)用軟件的重要性.重要性度量結(jié)果為向量R，滿足：

其中R(i)是應(yīng)用i的得分，流失因子ε ＜1，Bi是依賴應(yīng)用i的應(yīng)用軟件集合，E是重新分配和補(bǔ)充得分的方法，并且通過方法E來(lái)保持‖R‖1=1，E(i)是為應(yīng)用i補(bǔ)充的得分的初值（或稱為補(bǔ)充方案，εE(i)是真實(shí)的補(bǔ)充值）.

可以根據(jù)軟件生態(tài)圖構(gòu)造矩陣An×n（n是生態(tài)中應(yīng)用的個(gè)數(shù)）：將所有應(yīng)用軟件編號(hào)為1～n.對(duì)于1≤i≤n和1≤j≤n，如果應(yīng)用i被應(yīng)用j依賴，則Aij= 1 /Nj，Nj是應(yīng)用j依賴的應(yīng)用個(gè)數(shù)（點(diǎn)j的出度）；否則Aij=0.算法收斂后的向量R（第i維上的值是應(yīng)用i的得分）滿足R=AR.An×n稱為依賴關(guān)系矩陣.

算法1 展示了PackageRank 計(jì)算應(yīng)用軟件重要性的過程.

算法1.PackageRank 計(jì)算應(yīng)用軟件重要性R.

初始向量R0可以是任何滿足‖R‖1=1的向量，它并不影響最終收斂時(shí)的結(jié)果.本文采用等值向量作為初始向量，即

流失因子ε的大小會(huì)影響算法的計(jì)算結(jié)果.如果ε過大，依賴關(guān)系網(wǎng)在算法中的作用將被減弱，導(dǎo)致結(jié)果不準(zhǔn)確；如果過小，算法收斂速度更慢.Page 等人[21]建議ε=0.15，以表征網(wǎng)絡(luò)用戶隨機(jī)跳轉(zhuǎn)訪問網(wǎng)頁(yè)的概率；而由于ε在此處僅為避免排序沉沒，選取的值太大將帶來(lái)較大誤差，故本文設(shè)定ε=0.001.重新補(bǔ)充分配得分的方法是平均分配，這是因?yàn)閛pen Euler 缺乏其他與應(yīng)用軟件相關(guān)的統(tǒng)計(jì)數(shù)據(jù)或信息.

圖6 展示了排名前N的應(yīng)用軟件重要性（PackageRank 得分）之和隨N的變化曲線.相同應(yīng)用場(chǎng)景、不同體系結(jié)構(gòu)的軟件生態(tài)得到了形狀相似的結(jié)果曲線，但不同應(yīng)用場(chǎng)景的結(jié)果有明顯差異，這和第3 節(jié)中兼容分析的結(jié)論是相同的.

Fig.6 Importance of applications computed by PackageRank圖6 PackageRank 計(jì)算的應(yīng)用軟件重要性

不同應(yīng)用軟件的重要性得分差距很大，少量的應(yīng)用聚集了大量的重要性得分，同時(shí)很大一部分應(yīng)用的得分是極小的.圖6（a）（b）顯示，服務(wù)器生態(tài)中7 個(gè)應(yīng)用的重要性得分之和已經(jīng)達(dá)到全部應(yīng)用的25%，28 個(gè)應(yīng)用達(dá)到了50%，近800 個(gè)達(dá)到了75%，而生態(tài)中共有1.8 萬(wàn)余個(gè)應(yīng)用軟件；嵌入式生態(tài)的得分分布相對(duì)更加均衡，但也存在明顯的差距.

這一軟件生態(tài)的特點(diǎn)符合自然界生態(tài)系統(tǒng)的規(guī)律.少數(shù)食物鏈頂端的物種能得到大量的能量輸入，在系統(tǒng)中也更具支配性；而底端的低級(jí)生物只能靠更多的數(shù)量來(lái)維持平衡.軟件生態(tài)和自然界生態(tài)系統(tǒng)的發(fā)展過程有所相似，依賴關(guān)系網(wǎng)和食物鏈網(wǎng)也是類似的結(jié)構(gòu)，而PackageRank 的結(jié)果也正是自然界的生態(tài)規(guī)律在軟件生態(tài)中的延伸，這體現(xiàn)了算法的合理性.此外，嵌入式生態(tài)中的得分分布更為均衡的原因則是其生態(tài)規(guī)模更小、復(fù)雜度更低，重要的應(yīng)用不能積累足夠的分?jǐn)?shù)而與其他應(yīng)用拉開差距.

4.2.2 計(jì)算C 庫(kù)的兼容性

兼容性的度量方法應(yīng)當(dāng)體現(xiàn)應(yīng)用軟件重要性的差異.C 庫(kù)兼容更重要的應(yīng)用軟件，對(duì)生態(tài)的積極作用更顯著，C 庫(kù)的兼容性便得到更大幅度的提升；C庫(kù)不兼容重要應(yīng)用，對(duì)生態(tài)造成的破壞也更大，兼容性將受到更大的影響.因此，通過對(duì)被兼容應(yīng)用的重要性評(píng)價(jià)（PackageRank 得分）來(lái)計(jì)算兼容性是十分合適的.

雖然PackageRank 為每個(gè)應(yīng)用軟件輸出一個(gè)確定的得分，但如果將所有應(yīng)用軟件的得分縮放同樣的比例，得到的結(jié)果仍是穩(wěn)定的.通過改變定義5 中‖R‖1的值，就能實(shí)現(xiàn)得分的縮放.因此，得分的比值更具意義，它反映的是生態(tài)中各個(gè)應(yīng)用的“相對(duì)重要性”.這個(gè)屬性是應(yīng)用軟件生態(tài)的固有屬性，與得分的縮放無(wú)關(guān).我們采用所有被兼容應(yīng)用的重要性得分之和與全部應(yīng)用得分之和的比值來(lái)度量C 庫(kù)的兼容性.由于‖R‖1=1，故只需將所有被兼容應(yīng)用的得分求和便能得到這個(gè)比值.

定義6.C 庫(kù)在軟件生態(tài)內(nèi)的兼容性.兼容性定義為所有被兼容應(yīng)用的重要性得分之和與全部應(yīng)用得分之和的比值，即為所有被兼容應(yīng)用的得分之和.

表6 展示了musl libc 在openEuler 的4 種生態(tài)中的兼容性度量結(jié)果.

Table 6 Compatibility of musl libc表6 musl libc 的兼容性%

不同應(yīng)用場(chǎng)景的兼容性差別很大，而體系結(jié)構(gòu)對(duì)兼容性的影響很小.嵌入式生態(tài)的C 庫(kù)兼容性較服務(wù)器生態(tài)高出26%左右，而實(shí)際情況也確實(shí)如此，即嵌入式生態(tài)的應(yīng)用多為主流應(yīng)用，它們更多地調(diào)用常用的API，而缺失API 普遍是不常用且功能特殊的，因此應(yīng)用軟件調(diào)用缺失API 的概率更低.

至此，我們發(fā)現(xiàn)musl libc 對(duì)應(yīng)用軟件的兼容性仍有很大的提升空間，在替換前需要進(jìn)一步補(bǔ)全開發(fā)工作.

5 缺失API 優(yōu)先級(jí)算法

C 庫(kù)的開發(fā)者不僅需要了解C 庫(kù)的兼容性，而且更需要獲知缺失API 的優(yōu)先級(jí)，以便按序進(jìn)行補(bǔ)全.

缺失API 的優(yōu)先級(jí)差異體現(xiàn)在兼容性價(jià)值上：C庫(kù)通過補(bǔ)全API 而兼容更多應(yīng)用軟件運(yùn)行，不同API被應(yīng)用軟件調(diào)用的情況有差別，應(yīng)用軟件的重要性又有差別，從而補(bǔ)全不同的API 對(duì)生態(tài)的兼容性價(jià)值也有高低之分.

本節(jié)提出了有接口的軟件生態(tài)圖模型，并在該模型上提出了APIRank 算法以度量缺失API 優(yōu)先級(jí)，然后按照優(yōu)先級(jí)次序進(jìn)行了API 補(bǔ)全模擬.

5.1 影響缺失API 優(yōu)先級(jí)的因素

與4.1 節(jié)類似，缺失API 的優(yōu)先級(jí)也受多重因素的影響.被大量應(yīng)用軟件調(diào)用的缺失API 應(yīng)優(yōu)先實(shí)現(xiàn)，以滿足眾多應(yīng)用的功能需求；重要的應(yīng)用軟件調(diào)用的缺失API 應(yīng)優(yōu)先實(shí)現(xiàn)，以保證重要應(yīng)用的正常運(yùn)行.此外，如果一個(gè)應(yīng)用軟件調(diào)用的缺失API 數(shù)量過多，要兼容該應(yīng)用就需要大量的工作，兼容性提升效率降低，且開發(fā)過程不易調(diào)試[21]，故這些API 的優(yōu)先級(jí)降低.因此，缺失API 的優(yōu)先級(jí)受3 種因素的影響：

1）調(diào)用它的應(yīng)用軟件的數(shù)量；

2）調(diào)用它的應(yīng)用軟件的重要性；

3）調(diào)用它的應(yīng)用軟件所調(diào)用的缺失API 總數(shù).

5.2 APIRank 算法

為綜合考慮5.1 節(jié)所述的3 個(gè)因素，我們基于軟件生態(tài)圖和PackageRank 算法作進(jìn)一步延伸，提出了有接口的軟件生態(tài)圖模型和APIRank 算法以度量缺失API 的優(yōu)先級(jí).

在軟件生態(tài)圖中，應(yīng)用軟件之間的依賴關(guān)系對(duì)應(yīng)著圖中的有向邊.這種將依賴關(guān)系模型化的思路在有接口的軟件生態(tài)圖中得到了延續(xù).應(yīng)用軟件對(duì)API 的調(diào)用可以被視作一種廣義的“依賴”關(guān)系.應(yīng)用軟件“依賴”API，正如應(yīng)用軟件依賴其他應(yīng)用一樣.依照這個(gè)思路，可以構(gòu)造一張由應(yīng)用軟件和缺失API 共同組成的有向圖，并根據(jù)廣義依賴關(guān)系在圖中連接對(duì)應(yīng)的邊.我們把這樣的有向圖稱為有接口的軟件生態(tài)圖.

定義7.有接口的軟件生態(tài)圖.它是一張表示軟件生態(tài)中應(yīng)用軟件和缺失API 及其之間廣義依賴關(guān)系的有向圖.圖中的每個(gè)點(diǎn)對(duì)應(yīng)生態(tài)中的一個(gè)應(yīng)用軟件或一個(gè)缺失API，每條邊對(duì)應(yīng)一個(gè)廣義依賴關(guān)系，邊的方向規(guī)定為：應(yīng)用A依賴應(yīng)用B，對(duì)應(yīng)一條從A指向B的邊；應(yīng)用C調(diào)用缺失APID，對(duì)應(yīng)一條從C指向D的邊.

算法1 中的PackageRank 的計(jì)算過程同樣可以用于有接口的軟件生態(tài)圖，收斂后圖中每個(gè)結(jié)點(diǎn)也會(huì)有一個(gè)穩(wěn)定的得分.本文將收斂后代表缺失API 的結(jié)點(diǎn)的得分視為缺失API 的優(yōu)先級(jí)，這個(gè)算法稱為APIRank，如圖7 所示，它是圖4 添加了缺失的API 而生成的.

Fig.7 Illustration of APIRank圖7 APIRank 示意圖

APIRank 算法的含義是：

1）被更多應(yīng)用軟件調(diào)用的缺失API 有更多的分?jǐn)?shù)來(lái)源，從而獲得更高的分?jǐn)?shù)；

2）更重要的應(yīng)用有更高的分?jǐn)?shù)，它調(diào)用的缺失API 也能獲得更高的分?jǐn)?shù)；

3）調(diào)用多個(gè)缺失API 的應(yīng)用有更多的出邊，每個(gè)缺失API 能從出邊獲得的分?jǐn)?shù)更低.

由此可見，APIRank 算法兼顧了影響接口優(yōu)先級(jí)的3 個(gè)因素.

同樣地，可以根據(jù)有接口的軟件生態(tài)圖構(gòu)造矩陣A（n+m）×（n+m）（n是應(yīng)用個(gè)數(shù)，m是缺失API 個(gè)數(shù)）：所有應(yīng)用編號(hào)為1～n，所有缺失API 編號(hào)為n+1～n+m.對(duì)于1≤i≤n+m和1≤j≤n+m，如果點(diǎn)j有指向點(diǎn)i的邊，則Aij= 1 /Nj，Nj是點(diǎn)j的出度；否則Aij= 0.A（n+m）×（n+m）稱為廣義依賴關(guān)系矩陣.

算法2 展示了APIRank 計(jì)算缺失API 優(yōu)先級(jí)的過程.

算法2.APIRank 計(jì)算缺失API 優(yōu)先級(jí).

同樣地，APIRank 也采用等值向量作為初始向量，流失因子ε=0.001.

根據(jù)缺失API 的得分R的高低，可以對(duì)其優(yōu)先級(jí)進(jìn)行排序.

5.3 接口補(bǔ)全模擬

我們模擬了按照缺失API 優(yōu)先級(jí)排序進(jìn)行補(bǔ)全時(shí)，musl libc 兼容性隨著每個(gè)API 的補(bǔ)全而逐步提升的過程，如圖8 所示.

Fig.8 Increase of compatibility in simulations process of API complementation圖8 API 補(bǔ)全模擬過程中兼容性的提升過程

圖8 的結(jié)果顯示，musl libc 兼容性的提升呈階梯型，這是因?yàn)樵陂_發(fā)過程中往往需要實(shí)現(xiàn)多個(gè)API才能兼容某一個(gè)應(yīng)用軟件，而該應(yīng)用軟件的兼容能夠（或許會(huì)大幅度地）提升C 庫(kù)的兼容性.同一應(yīng)用場(chǎng)景、不同體系結(jié)構(gòu)的兼容性提升過程相似，而不同應(yīng)用場(chǎng)景的過程區(qū)別較大，這也完全符合我們的預(yù)期.

注意到，當(dāng)C 庫(kù)達(dá)到完全兼容（兼容性為100%）時(shí)，并非所有的缺失API 均已被補(bǔ)全，即代表完全兼容的點(diǎn)的橫坐標(biāo)值均小于表2 中的主要接口缺失總數(shù)（1 379）.這表明有些缺失API 未被生態(tài)中的任何應(yīng)用軟件調(diào)用.根據(jù)本文對(duì)兼容的定義，這些缺失API 沒有對(duì)應(yīng)用軟件生態(tài)提供任何有效的兼容支持，目前并不需要補(bǔ)全它們就能達(dá)到完全兼容，它們也不包含在有接口的軟件生態(tài)圖中，從而不存在APIRank 算法得分（無(wú)優(yōu)先級(jí)）.

圖9 展示了被調(diào)用和未被調(diào)用的缺失API 數(shù)量和占比.我們發(fā)現(xiàn)未被調(diào)用的API 所占的比例很高：嵌入式生態(tài)中有95.9%的缺失接口未被應(yīng)用軟件調(diào)用過；服務(wù)器生態(tài)中，aarch64 和x86_64 的數(shù)據(jù)分別是85.3%和85.1%.API 未被任何應(yīng)用軟件調(diào)用，一般是因?yàn)槠涔δ苓^于特殊而缺乏實(shí)用場(chǎng)景，或存在與其功能類似但更受應(yīng)用開發(fā)者喜愛（性能更好，更符合編程習(xí)慣等原因）的其他API.嵌入式生態(tài)的比例比服務(wù)器生態(tài)低10%，而這也和嵌入式生態(tài)的兼容性更高（見表6）相呼應(yīng).

Fig.9 Proportion of called missing API and not called missing API圖9 被調(diào)用和未被調(diào)用的缺失API 占比

openEuler 的C 庫(kù)開發(fā)者當(dāng)前無(wú)需擔(dān)心這些未被調(diào)用的API 會(huì)帶來(lái)兼容性問題.而且，目前未被調(diào)用的API 短期內(nèi)也很可能不會(huì)被應(yīng)用軟件的開發(fā)者使用，因此C 庫(kù)開發(fā)者有較長(zhǎng)的時(shí)間來(lái)逐一補(bǔ)全它們（如果需要），同時(shí)該C 庫(kù)又能不受影響地提供服務(wù).

6 評(píng) 估

本節(jié)評(píng)估了PackageRank 算法和APIRank 算法的效果，分析算法誤差，對(duì)比其他現(xiàn)有算法，展望算法的延伸，以及闡明本文研究的局限.

6.1 算法效果

6.1.1 PackageRank 算法效果

PackageRank 算法的評(píng)估采用aarch64 體系結(jié)構(gòu)的結(jié)果作為例子.表7 給出了在aarch64 的2 種應(yīng)用場(chǎng)景下PackageRank 得分排名較高的應(yīng)用的分值.為了更清晰地顯示結(jié)果，表7 中的得分是經(jīng)過等比例放大的，這樣的放大并不影響算法結(jié)果的穩(wěn)定和準(zhǔn)確.

Table 7 Statistics of High-ranked Applications of PackageRank in aarch64表7 aarch64 體系結(jié)構(gòu)下PackageRank 高優(yōu)先級(jí)應(yīng)用的統(tǒng)計(jì)

PackageRank 考慮了影響應(yīng)用軟件重要性的2 個(gè)因素：被依賴次數(shù)、依賴應(yīng)用的重要性.由表7 可知，這2 個(gè)因素實(shí)際都對(duì)結(jié)果產(chǎn)生了影響.服務(wù)器生態(tài)中，bash，texlive-base 都既被大量應(yīng)用依賴（入邊數(shù)很高），又被高分應(yīng)用依賴并獲得了大量得分（最大入邊分?jǐn)?shù)高，最大入邊分?jǐn)?shù)來(lái)源的分?jǐn)?shù)和排名高）；texlivekpathsea 是典型的僅因大量應(yīng)用依賴而積累出高分的例子，有3 190 個(gè)依賴它的應(yīng)用，但其中最高得分的應(yīng)用也僅排名65；ncurses-base 則完全因?yàn)楦叻謶?yīng)用的依賴才成為了排名第3 的應(yīng)用，它只有2 個(gè)依賴者，而其中ncurse-libs 為它輸送了96.9%（3 487.70/3 598.00）的高額分?jǐn)?shù).嵌入式生態(tài)中，bash 受2 種因素影響而排名第1，zlib，libselinux 主要因?yàn)楸灰蕾嚧螖?shù)高，而libsepol 則主要因?yàn)閺膌ibselinux（排名第4）處獲得大量分?jǐn)?shù)而排在第3 位.

此外，服務(wù)器生態(tài)中的perl-libs 和perl-Exporter存在雙向依賴，這是排序沉沒問題出現(xiàn)的例子，在算法中已經(jīng)解決了這個(gè)問題（4.2 節(jié)）.

應(yīng)當(dāng)指出，平均入邊分?jǐn)?shù)與入邊數(shù)的乘積并不等于得分，而是約等于得分減1（存在微小誤差）.這是因?yàn)镻ackageRank 在迭代時(shí)對(duì)每個(gè)點(diǎn)進(jìn)行了等額的得分補(bǔ)充（4.2 節(jié)）.補(bǔ)充的得分并不來(lái)自入邊，而表7 中的得分就是將這部分補(bǔ)充的得分縮放為1.00后的結(jié)果.

上述分析表明PackageRank 算法有效地實(shí)現(xiàn)了對(duì)應(yīng)用軟件重要性的多重影響因素的兼顧.

6.1.2 APIRank 算法效果

APIRank 算法的評(píng)估采用x86_64 體系結(jié)構(gòu)的結(jié)果作為例子.表8 列出了在x86_64 的2 種應(yīng)用場(chǎng)景下APIRank 算法中優(yōu)先級(jí)較高的API 的分值.

Table 8 Statistics of High-ranked APIs of APIRank in x86_64表8 x86_64 體系結(jié)構(gòu)下APIRank 高優(yōu)先級(jí)API 的統(tǒng)計(jì)

服務(wù)器生態(tài)中，應(yīng)用軟件的高分對(duì)其所調(diào)用的缺失API 的優(yōu)先級(jí)提升作用明顯：PackageRank 中排名第1 的coreutils 調(diào)用了6 個(gè)缺失API，它們均排在前7 名中.另一方面，被大量應(yīng)用軟件調(diào)用也能提升API 優(yōu)先級(jí)，fcntl64 有遠(yuǎn)超其他API 的被調(diào)用數(shù)（入邊數(shù)），這也使得它排在第2 名.另外一個(gè)例子則能體現(xiàn)這2 個(gè)因素對(duì)優(yōu)先級(jí)的共同影響：dlvsym 和argz_add 得分接近，但分別主要受被調(diào)用數(shù)和調(diào)用者重要性的因素影響，表明在不同主要因素影響下缺失API 也能得到相近的分?jǐn)?shù).

嵌入式生態(tài)結(jié)構(gòu)比較簡(jiǎn)單，且其應(yīng)用軟件調(diào)用的缺失API 數(shù)量更少，因此API 優(yōu)先級(jí)得分比較接近，但仍能看出多個(gè)因素共同影響優(yōu)先級(jí)的效果.特別地，mallinfo 和obstack_vprintf 的得分接近，前者的被調(diào)用數(shù)和調(diào)用者最高得分都更高（3 對(duì)1，3.26 對(duì)1.00），但其調(diào)用者（e2fsprogs）所調(diào)用的總?cè)笔PI 數(shù)更多（4 個(gè)，另外1 條出邊是應(yīng)用依賴關(guān)系），故其得分與后者接近，這體現(xiàn)了第3 個(gè)因素對(duì)結(jié)果的影響.

上述分析表明APIRank 算法有效地實(shí)現(xiàn)了對(duì)缺失API 優(yōu)先級(jí)的多重影響因素的兼顧.

6.2 算法誤差

本文算法的誤差有2 個(gè)來(lái)源：

1）流失因子ε和得分補(bǔ)充.本文中ε=0.001，得分補(bǔ)充方法為平均分配，因此在每輪迭代后有0.1%的分?jǐn)?shù)從各個(gè)結(jié)點(diǎn)中流失，并平均分配到所有結(jié)點(diǎn).因此，兼容性誤差在0.1%以內(nèi)；缺失API 優(yōu)先級(jí)的數(shù)值存在誤差，但排序不存在誤差，即按比例流失和平均分配不影響得分之間的大小關(guān)系.

2）收斂極限的設(shè)定.本文收斂極限設(shè)定為“迭代向量差的2-范數(shù)不超過10-5”，因此兼容性的誤差在0.001%以內(nèi)，缺失API 優(yōu)先級(jí)的平均誤差在10-7以內(nèi).

綜上，兼容性誤差在0.1%以內(nèi)，缺失API 優(yōu)先級(jí)的平均誤差在10-7以內(nèi).由于在4 種生態(tài)內(nèi)的所有缺失API 的優(yōu)先級(jí)得分均高于10-5，故APIRank 的平均誤差低于1%.

6.3 算法對(duì)比

第4 節(jié)提出了本文的兼容性算法PackageRank，而1.3 節(jié)中也提到了其他2 種兼容性度量方法.

1）算法A：已實(shí)現(xiàn)的API 個(gè)數(shù)；

2）算法B：文獻(xiàn)[2]的加權(quán)完整性.

算法A的度量方式因缺乏應(yīng)用軟件所包含的信息而不準(zhǔn)確，在本節(jié)中不再討論.

算法B是將其他系統(tǒng)與Ubuntu 15.04 作比較，或模擬將系統(tǒng)構(gòu)件安裝在Ubuntu 15.04 上并研究其兼容性.之所以選擇Ubuntu 15.04 為基準(zhǔn)系統(tǒng)，是因?yàn)樗恰肮芾砹己玫摹V泛支持應(yīng)用軟件的、統(tǒng)計(jì)軟件包安裝數(shù)據(jù)的Linux 發(fā)行版”.文獻(xiàn)[2]統(tǒng)計(jì)API 調(diào)用情況時(shí)使用Ubuntu 的RPM 包，API 重要性和加權(quán)完整性的計(jì)算也均采用Ubuntu 的安裝次數(shù)統(tǒng)計(jì).

我們認(rèn)為算法B不適用于openEuler 對(duì)musl libc兼容性分析的原因是：

1）openEuler 的應(yīng)用軟件生態(tài)與Ubuntu 有區(qū)別，RPM 包的內(nèi)容也有所不同；

2）openEuler 不具備像Ubuntu 一樣完備的應(yīng)用軟件安裝記錄；

3）應(yīng)用軟件的安裝并非獨(dú)立事件，而是存在互相依賴關(guān)系.

表9 列出了通過各種算法計(jì)算的musl libc 兼容性.其中，“算法B”一欄是文獻(xiàn)[2]給出的度量結(jié)果，而“算法B*”一欄是將算法B的基準(zhǔn)系統(tǒng)設(shè)定為open-Euler 得到的結(jié)果.由于不具備安裝次數(shù)統(tǒng)計(jì)，我們?cè)谒惴˙*中將下載次數(shù)設(shè)為相同.按照算法2 的定義，此時(shí)計(jì)算的兼容性值即為應(yīng)用軟件的兼容率.如第4節(jié)所言，兼容率不能準(zhǔn)確地反映兼容性，因此在缺乏數(shù)據(jù)統(tǒng)計(jì)時(shí)，本文提出的兼容性算法比算法B更為準(zhǔn)確.

對(duì)比其他算法，本文提出的PackageRank 算法的優(yōu)勢(shì)和特點(diǎn)在于：

1）為系統(tǒng)提供從自身應(yīng)用軟件生態(tài)出發(fā)的、個(gè)性化的兼容性評(píng)估.不同系統(tǒng)能夠搭載的應(yīng)用軟件范圍（即生態(tài)）不同（Ubuntu/Debian 生態(tài)中有30 976 個(gè)應(yīng)用[2]，openEuler x86_64 服務(wù)器生態(tài)有18 288 個(gè)，open-Euler x86_64 嵌入式生態(tài)有83 個(gè)），很難為多種多樣的系統(tǒng)確定統(tǒng)一的“基準(zhǔn)生態(tài)”.本文的算法以每種系統(tǒng)或構(gòu)件各自的應(yīng)用軟件生態(tài)信息作為輸入，反映API 在其真實(shí)應(yīng)用場(chǎng)景的兼容性，為開發(fā)者提供準(zhǔn)確的、個(gè)性化的評(píng)估結(jié)果.

2）適用于缺乏應(yīng)用軟件安裝統(tǒng)計(jì)的系統(tǒng).包括openEuler 在內(nèi)的大多數(shù)操作系統(tǒng)的發(fā)行版都不具備像Ubuntu/Debian 一樣完備的應(yīng)用軟件安裝記錄.即使存在統(tǒng)計(jì)數(shù)據(jù)，如果數(shù)據(jù)量不足而不能視為滿足“大數(shù)定律”，那么“用頻率估計(jì)概率”也并不準(zhǔn)確.在統(tǒng)計(jì)數(shù)據(jù)缺失時(shí)，本文提出的算法既能夠利用有限的信息，又能緊密結(jié)合API 的調(diào)用情況，準(zhǔn)確地度量兼容性.算法所需的信息僅是應(yīng)用軟件的RPM 包.對(duì)于大多數(shù)系統(tǒng)而言，它們的生態(tài)中應(yīng)用軟件的RPM包都是完整且容易獲取的.

APIRank 的優(yōu)勢(shì)和特點(diǎn)除包含前述內(nèi)容外還有：面向仍有開發(fā)需求的系統(tǒng)和構(gòu)件，為API 的補(bǔ)全實(shí)現(xiàn)工作提供幫助.現(xiàn)有研究大多面向已經(jīng)完整實(shí)現(xiàn)的系統(tǒng)和構(gòu)件，分析已有API，而本文的算法僅度量缺失API 的優(yōu)先級(jí)，為仍需開發(fā)的系統(tǒng)和構(gòu)件提供補(bǔ)全順序的建議.本文算法并非為L(zhǎng)inux API 的全局現(xiàn)狀和生態(tài)環(huán)境做分析，而是為系統(tǒng)和構(gòu)件開發(fā)者提供方案建議.

6.4 展 望

1）目前并沒有將PackageRank 和APIRank 應(yīng)用于完整開發(fā)過程的例子，但openEuler 已經(jīng)開始按照APIRank 計(jì)算出的優(yōu)先級(jí)順序開展補(bǔ)全工作.在開發(fā)過程中發(fā)現(xiàn)，有些高優(yōu)先級(jí)API 并非在musl libc 中實(shí)現(xiàn)，而是以別名實(shí)現(xiàn)（如error）或在其他分支庫(kù)中實(shí)現(xiàn)（如backtrace），這表明高優(yōu)先級(jí)API 在musl libc 的開發(fā)者看來(lái)也十分重要，因此他們沒有拒絕實(shí)現(xiàn)這些API，只是其實(shí)現(xiàn)細(xì)節(jié)與glibc 存在區(qū)別.APIRank的分析結(jié)果和musl libc 開發(fā)者的觀點(diǎn)存在一致，有望為補(bǔ)全工作提供準(zhǔn)確的信息和實(shí)質(zhì)性的幫助.

2）在PackageRank 和APIRank 中，除應(yīng)用軟件全集外，系統(tǒng)開發(fā)者還可以選擇將某個(gè)目標(biāo)應(yīng)用集作為研究對(duì)象，從而獲知系統(tǒng)或構(gòu)件對(duì)該目標(biāo)集的兼容性和缺失API 優(yōu)先級(jí).

3）PackageRank 和APIRank 不針對(duì)某種特定系統(tǒng)或構(gòu)件，因此它們有望適用于其他場(chǎng)景下的API兼容性分析，如其他C 庫(kù)、系統(tǒng)調(diào)用、向量化參數(shù)等.此外，還有望將它們應(yīng)用于系統(tǒng)模擬器的兼容性度量.

6.5 局 限

1）有2 處假設(shè)存在不準(zhǔn)確性：應(yīng)用的可執(zhí)行文件存在可鏈接API 的符號(hào)表?xiàng)l目，即視為API 被調(diào)用；API 存在即視為API 能正確工作.在3.1 節(jié)中，已經(jīng)對(duì)它們的不準(zhǔn)確性做出說(shuō)明.

2）僅采用靜態(tài)分析而未考慮API 調(diào)用頻率等其他有關(guān)API 調(diào)用的信息，而靜態(tài)分析方法也無(wú)法準(zhǔn)確給出這些信息.

3）沒有參考用戶對(duì)應(yīng)用軟件的使用喜好和傾向，包括應(yīng)用軟件之間的其他隱性關(guān)聯(lián).

4）未全面考慮編譯環(huán)境和源碼對(duì)API 調(diào)用情況的影響，即應(yīng)用軟件的開發(fā)者可能會(huì)通過宏命令，根據(jù)編譯環(huán)境的不同而調(diào)用不同的接口（特別是那些不在ANSI/ISO C 標(biāo)準(zhǔn)中的接口）.應(yīng)用軟件的編譯環(huán)境會(huì)影響接口調(diào)用，接口缺失仍存在誤判.

5）實(shí)驗(yàn)對(duì)象單一.本文的算法僅在openEuler 上的musl libc 兼容性研究中使用，未曾在其他系統(tǒng)或構(gòu)件上開展工作.

7 結(jié)束語(yǔ)

本文研究了openEuler 的4 種軟件生態(tài)中的musl libc 兼容性和缺失API 優(yōu)先級(jí)，以幫助openEuler 的C 庫(kù)開發(fā)者進(jìn)行接口補(bǔ)全工作.

本文的分析結(jié)果表明：一方面，musl libc 目前的兼容性仍有待提高，若要用其替代glibc 則需要進(jìn)一步開發(fā)；另一方面，開發(fā)者可以根據(jù)本文的缺失API優(yōu)先級(jí)按序而高效地開展工作.

本文基于應(yīng)用之間的依賴關(guān)系和應(yīng)用對(duì)API 的調(diào)用關(guān)系進(jìn)行兼容性和缺失API 優(yōu)先級(jí)的度量.從依賴關(guān)系和調(diào)用關(guān)系到兼容性和優(yōu)先級(jí)的轉(zhuǎn)化，是本文的核心思想和成果.

作者貢獻(xiàn)聲明：吳亦澤提出算法、完成實(shí)驗(yàn)并撰寫論文；于佳耕提出算法思路和指導(dǎo)意見并修改論文；鄭晨提出指導(dǎo)意見并修改論文；武延軍給出選題、提出指導(dǎo)意見并修改論文.