openEuler 中C 標準庫替換的兼容性分析

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

1 （中國科學院軟件研究所 北京 100190）

2 （中國科學院大學 北京 101408）

3 （計算機科學國家重點實驗室（中國科學院軟件研究所）北京 100190）

應用程序編程接口（application programming interface，API）是為其他軟件提供服務的軟件接口[1]，將計算機與軟件或軟件與軟件連接，為軟件開發者提供幫助.應用軟件使用操作系統提供的功能時，需要調用操作系統提供的API.在Linux 各發行版中，為了讓應用開發者能更方便地使用系統API 以實現更復雜的功能，系統將API 進一步封裝至C 標準庫（本文簡稱C 庫）中，并將C 庫的API 供用戶調用.C 庫連接了應用軟件和操作系統，C 庫的接口實現影響應用軟件對系統功能的使用.如果應用軟件不能通過調用C庫接口來和系統建立聯系，很多關鍵的應用功能也將無法實現.

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

為了避免系統搭載的C 庫因開源協議而在商業化場景下帶來問題，開源歐拉（openEuler）操作系統商業發行版的開發者正在考慮用musl libc 替換glibc.musl libc 是一個使用MIT 許可證的輕量級C 庫，MIT許可證在有版權聲明的條件下允許任意地使用、復制、修改和散布軟件而無需開源.musl libc 可用于從小型嵌入式系統到通用桌面、服務器系統的很多場景，具有體量小、魯棒性和安全性強、易于裝載等優勢.因其基礎架構較為成熟，使用的協議也適用于商業場景，故musl libc 成為替換glibc 的首要選擇.

新C 庫對原有應用軟件的兼容是C 庫替換工作的關鍵——新C 庫應當保證在原有C 庫下能正確運行的應用軟件在替換后也能正確運行.目前，musl libc 相比glibc 有較多功能缺失，如果直接進行替換，將導致C 庫對應用軟件的兼容性較低，而低兼容性嚴重影響操作系統提供的服務質量，降低商業系統的市場競爭力.因此，在替換前需要通過補全開發將musl libc 的兼容性提高到足夠高的水平.

兼容性分析對新C 庫的開發很有幫助[2]，然而現有的兼容性分析方法并不適用于openEuler 對musl libc 的補全工作（見1.3 節和6.3 節）.針對這個問題，本文提出新的兼容性分析算法來研究openEuler 的4 種主要軟件生態中的musl libc 兼容性和缺失API 優先級.本文的研究目的是幫助openEuler 的C 庫開發者了解musl libc 在openEuler 操作系統上的兼容性，并參照優先級順序補全開發接口，合理安排開發工作.

本文的主要貢獻有4 個方面：

1）量化對比了musl libc 與glibc 的接口.根據接口開發現狀，將全部接口劃分為主要接口和非主要接口，并分別進行接口對比分析，量化了musl libc 和glibc 的接口差異和重合率，論證了對musl libc 進行補全的必要性和可行性.

2）量化分析了musl libc 對應用軟件生態的兼容情況.根據應用軟件對缺失API 的調用情況和應用之間的依賴關系提出了兼容的定義，將依賴關系構建為圖模型，將兼容的定義形式化，并統計分析了應用軟件生態的兼容情況.

3）提出了兼容性度量算法——PackageRank.PackageRank 在圖模型上為應用軟件賦分，并通過計算兼容應用的得分占比來度量兼容性.

4）提出了缺失API 優先級算法——APIRank.APIRank 是PackageRank 的延伸，根據缺失API 被應用軟件調用的情況，對圖模型作出進一步擴展，并在新的圖模型上為API 賦分，以度量缺失API 的優先級.

1 相關工作

1.1 C 標準庫

除glibc 和musl libc 外，還有多種其他C 標準庫的實現，如eglibc，uClibc，dietlibc 等.eglibc 是glibc 的一個分支，專為嵌入式場景設計，嚴格兼容二進制的glibc，使用LGPL v2.1 協議，2014 年初停止開發；uClibc為嵌入式Linux 系統開發，其迎合小型C 庫需求，使用LGPL v2.1 協議，自2012 年5 月以來未有新發行版本；dietlibc 適用于小型場景，可以為多種體系結構的Linux系統提供靜態鏈接二進制庫，使用GPL v2 協議，最新版本于2018 年9 月發行，版本間隔為4～5 年.相較之下，musl libc 使用MIT 協議，版本更新周期為6～12個月，最新版本發布于2022 年4 月.

musl libc 官方發布了對自己C 庫的兼容性分析報告[3]，將musl libc（1.1.24）與多種C 語言標準和其他C 庫進行了比較.分析顯示，musl libc 對POSIX 2008，C99，C11 標準的兼容性良好，分別有12 個、2 個、88個API 未實現，對比POSIX 2008 標準有2 個API 有函數原型但沒有實現.在與glibc，uClibc，dietlibc 進行對比時，musl libc 的魯棒性、安全性、構建環境適配性均優于其他C 庫；性能和體系結構適配性略低于glibc 而遠優于uClibc 和dietlibc；體量略大于dietlibc，略小于uClibc，遠小于glibc.此外，musl libc 在I/O、信號處理、正則表達式功能和動態鏈接等方面與glibc存在功能性差異.

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

Fig.1 Experimental results of performance and memory usage on glibc and musl libc圖1 glibc 與musl libc 的性能和內存占有量實驗結果

數據顯示，musl libc 在27 個測試中僅有3 個的性能比glibc 更高（運行時間更短），而內存占有量則有24 個更?。ㄇ一径加忻黠@的優勢）.這表明，雖然musl libc 的性能仍需提升，但其內存占有量低，因此補全開發工作將更為方便和靈活.

綜合以上分析，musl libc 架構成熟，許可協議對商用友好，適合進行補全開發和C 庫替換.另一方面，性能較低、功能有差別和缺陷等問題使得直接替換并不可行，補全開發工作是必要的.

1.2 openEuler

openEuler 是一個開源、免費的Linux 發行版平臺，它通過開放形式的社區與全球的開發者共同構建一個開放、多元和架構包容的軟件生態體系.2020年3 月，openEuler 社區正式發布了首個長期支持版本——openEuler 20.03 LTS，并與多家操作系統廠商共同發布了基于openEuler 的商業系統發行版.openEuler每6 個月發布一個社區創新版本，提供6 個月社區支持，而LTS 版本的發布間隔周期為2 年，提供4 年社區支持.目前，openEuler 22.03 LTS 已經發布，有多家國內外機構宣布將推出基于openEuler 22.03 LTS 的商業發行版.

1.3 兼容性研究

在兼容性度量方法中，一種簡單而直接的方法是計數滿足兼容條件的API 個數[5-8].其算法比較容易實現，但缺乏準確性，即只關注API 本身是否兼容，并未考慮真實場景的API 調用情況.

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

文獻[2]以Ubuntu 15.04 為基準，分析了其他一些Linux 類系統或構件（系統調用、C 庫、文件系統等）的API 重要性（API importance）和加權完整性（weighted completeness）.文獻[2]的作者認為“產生兼容性度量不準確問題的根本原因是缺乏對系統API 在實際中被調用情況的數據統計和分析”.該文獻利用Ubuntu/Debian 的應用軟件安裝次數統計，從概率角度度量其他系統或構件的兼容性.該文提出2個度量概念：

1）API 重要性.一部操作系統上會安裝多個應用軟件，這樣的一個“安裝集”是該文獻統計的基本單位.API 的重要性定義為“調用該API 的應用被安裝的概率”.一個應用軟件被安裝的概率是包含該應用的安裝集個數（該應用的安裝次數）與所有安裝集個數（即系統總安裝次數）的比值，將不同應用軟件的安裝視為獨立事件，便可以通過將所有調用某個API 的應用軟件的安裝概率相乘，來計算API 重要性.

2）加權完整性.加權完整性用于度量系統或構件對應用的兼容性.應用軟件分為被支持的（supported）和不被支持的（unsupported），而加權完整性的定義為“安裝集中被支持應用數量占該集中所有應用數量的比值的數學期望”.仍將不同應用軟件的安裝視為獨立事件，便能計算出加權完整性的估計值.

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

本文采用靜態分析度量兼容性，此外還可以采用動態分析或靜態和動態分析結合的方法.文獻[2]也采用了靜態分析度量系統和構件的兼容性，Cui 等人[17]利用動態二進制翻譯（dynamic binary translation）技術分析了Intel SGX Enclaves 的系統調用的兼容性，Atlidakis 等人[18]將靜態和動態結合來分析POSIX標準是否仍符合現代應用的需求.鄭煒等人[19]總結了近年來安卓移動應用兼容性的靜態和動態分析方法.動態分析收集程序的運行時數據，比靜態分析更加接近實際場景，但往往又無法準確模擬程序實際工作時的行為.在兼容性研究中，測試用例的選取不當會導致兼容問題不能在測試中暴露，降低兼容性分析的準確性.

2 musl libc 與glibc 的接口對比

本節將進行musl libc 與glibc 的接口對比分析.本節的結果是本文后續內容的基礎和依據.

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

Table 1 Versions and Repository Addresses of C Libraries表1 C 庫的版本號與倉庫地址

2.1 接口名稱提取

鏈接器在鏈接時需要知道庫文件內部定義了哪些接口，這要求被鏈接接口的信息必須完整保存在庫文件的符號表中.因此，可以從庫文件的符號表內提取接口名稱.

本文研究中的接口名稱提取自C 庫中的可執行文件（executable and linkable format，ELF）.具體方法為：遍歷C 庫所在目錄中的所有文件，讀取其中每個ELF的符號表.對于每個符號表項，如果其類型（type）為FUNC 或IFUNC 且可見度（bind）為GLOBAL 或 WEAK，則提取其符號名（name）.這樣提取的接口名稱僅包含可被鏈接的接口，而不可鏈接的接口與C 庫的兼容無關（僅定義在內部，不能被應用軟件調用），故不在本文的研究范圍內.

經過提取，glibc 共有6 466 個接口，musl libc 共有1 898 個.

2.2 主要接口

C 庫的接口有這樣的命名習慣：以字母起始的接口供用戶調用，以下劃線起始的接口實現內部和底層的功能（與操作系統交互、初始化和退出、編譯優化等）.例如，printf 是標準輸出的常用接口，而__libc_start_main 是C 程序初始化啟動的一部分，gcc 在編譯時可能會將printf 替換為_printf_chk 以防止棧溢出[2].本文將名稱以字母起始的接口稱為主要接口.

應用軟件開發者應該避免直接調用非主要接口[20]，故C 庫的底層差異不會導致兼容問題.然而，在靜態分析應用軟件對接口的調用情況時，非主要接口可能會帶來兼容性的誤判.例如，應用軟件調用的printf在gcc 編譯時被替換為_printf_chk，由于musl libc 未實現_printf_chk，所以分析結果將顯示該應用軟件調用了未實現的接口，從而存在兼容問題.但是，如果使用musl-gcc 編譯，程序可以正確鏈接musl libc 的printf 接口，所以兼容問題實際上并不存在.

雖然本文的研究角度是二進制兼容，但這樣的誤判將導致兼容性分析結果不準確，這是我們希望避免的.因此，本文在兼容性度量時只對主要接口做統計和分析.除特別注明外，后文中所述的結果均以主要接口為研究對象.

經篩選，glibc 有2 883 個主要接口，musl libc 有1 516 個.

2.3 接口對比分析

全部接口和主要接口的統計結果見表2.除接口數量外，為比較C 庫的接口實現相似度，表2 還統計了接口重合率，即C 庫的共同接口數與該C 庫在該項的總接口數的比值.

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

結果顯示，2 個C 庫的主要接口重合率均遠高于各自的非主要接口重合率（glibc：52.2%和5.6%；musl libc：99.2%和52.1%）.這表明C 庫頂層接口的相似度較高，而底層實現區別較大.此外，glibc 中55%（3 583/6 466）的接口為非主要接口，可見其底層實現十分復雜，大量的非主要接口將嚴重影響接口對比結果的準確性，對后續的分析也不利，而只分析主要接口便能避免這個問題.

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

表3 列出的12 個主要接口是musl libc 獨有的.我們在統計應用軟件調用接口的情況（具體方法見第3 節）后發現，這12 個接口均未被任何應用軟件調用.值得一提的是，接口strlcat 和strlcpy 其實在應用軟件中十分常見，雖然glibc 并未實現這2 個接口，但應用開發者仍會想辦法使用它們：有些開發者將它們實現在自己的鏈接庫中（例如x86_64 的multipathtools-0.8.5-7，strlcpy），有些靜態鏈接了他們自己編寫的函數（例如aarch64 的entr-4.5-1，strlcpy）.也正因如此，這些應用軟件才能夠在glibc 下正確調用這2 個接口.

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

musl libc 相比glibc 有1 379 個主要接口尚未實現，但它們的情況與musl libc 獨有的12 個接口截然不同.由于glibc 的廣泛使用，應用軟件開發者一般都遵循glibc 的規范而進行相應的編程適配.如果開發者認為glibc 已經實現了某個接口，他們大多會選擇直接調用它而不會再自行實現該接口，因為非標準實現不僅帶來了更大的工作量，而且存在安全性隱患，也不利于代碼復用和移植.然而，開發者想要調用的接口可能是musl libc 未實現的，這便引發了musl libc 的兼容性問題.

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

3 應用軟件生態兼容分析

應用軟件生態是指系統上可運行的所有應用軟件的集合，本文中簡稱為軟件生態或生態.不同系統的應用軟件生態不同，故C 庫的兼容情況也有區別.本文研究musl libc 在openEuler 操作系統的4 種軟件生態中的兼容性，軟件生態分別為aarch64 服務器、x86_64 服務器、aarch64 嵌入式和x86_64 嵌入式.

openEuler 軟件生態中的應用軟件均可通過RPM（RedHat package manager）格式的軟件包安裝.RPM 包中含有應用軟件安裝所需的文件和信息，包括ELF、文檔、協議等.為提高結果的準確性，本文所統計和分析的應用軟件生態均排除了glibc 和musl libc 的基本包與擴展包，如表4 所示.

Table 4 Basic Package and Extended Package of C Libraries表4 C 庫的基本包與擴展包

本節將介紹C 庫兼容應用軟件的定義，并依照此定義分析4 種生態中的應用軟件兼容情況.

3.1 直接兼容的定義

兼容的直觀判定標準是，新C 庫能否保證應用軟件的全部可執行文件正確運行.C 庫無法支持可執行文件正確運行的原因有很多，被調用的接口未實現、實現的功能有缺陷或錯誤、應用開發者編程錯誤、鏈接器有漏洞等都是可能的原因.本文只考慮C庫未實現需要調用的接口的情況，即只要C 庫實現了應用軟件調用的接口，就認為該調用不會發生錯誤.另一方面，如果C 庫未實現需要調用的接口，本文也假設應用軟件開發者未在別處（如自行開發的鏈接庫中）實現這些接口（2.3 節中解釋了這樣假設的合理性）.

既然C 庫接口不會被自行實現，那么應用軟件調用的庫接口便完全依賴C 庫提供.因此，如果C 庫要保證應用軟件不出現錯誤，就必須實現應用軟件調用的全部接口.這種“保證”是C 庫對應用軟件的直接支持，本文將其稱為直接兼容.

定義1.C 庫直接不兼容應用軟件.如果在該應用軟件的RPM 包中存在某個ELF，該ELF 調用了C庫缺失的接口，則C 庫直接不兼容該應用軟件.如果不滿足上述條件，則C 庫直接兼容該應用軟件.

上述的接口“調用”指的是靜態調用，即ELF 的符號表中存在能夠動態鏈接該接口的條目.提取符號表中動態鏈接項的符號名，便提取出了所調用接口的名稱.

然而，即使“調用”了C 庫缺失的接口，ELF 運行時也未必會發生錯誤，因為執行流可能并不會經過這個接口.例如，某個負責崩潰處理功能的接口在符號表中有相應的項，但若程序未遇到崩潰，便不會真正調用它.因此，即使存在對缺失接口的“調用”，應用軟件在運行時也未必出現錯誤.

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

3.2 不兼容的傳遞性

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

應用軟件的兼容與否和它所依賴的其他應用軟件有關.對于某個應用軟件，即使它所依賴的應用軟件使用C 庫時都能正確運行，它也未必能正確運行，故“應用是否被兼容”和“所依賴應用是否被兼容”沒有直接關系.但反之，如果所依賴的應用不能正確運行，應用軟件本身的正確運行便也無法得到保證，則是一個因果關系.

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

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

3.3 兼容的定義

從3.1 節的直接兼容和3.2 節中的不兼容傳遞性出發，可以對C 庫兼容應用軟件做出定義.

定義2.C 庫是否兼容應用軟件.

1）如果C 庫直接不兼容一個應用軟件，則C 庫不兼容該應用軟件.

2）如果C 庫不兼容一個應用軟件所依賴的某個應用軟件，則C 庫不兼容該應用軟件.

3）如果無法通過以上2 條定義證明C 庫不兼容一個應用軟件，則C 庫兼容該應用軟件.

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

定義2也是無歧義的.該定義將應用軟件嚴格分為兼容的和不兼容的，不存在一個應用可以同時被判定為兼容和不兼容的情況.這是非常重要的，因為模糊的定義將從根本上降低兼容性分析結果的準確性.

3.4 軟件生態圖

定義2是自然語言表述的兼容定義，不利于直接用于判定應用軟件是否兼容.數學化的模型在判定時將更為有效.

應用軟件之間的依賴關系存在方向性.由此，可以將整個軟件生態視為一張有向圖，應用軟件與圖中的點一一對應，而依賴關系與圖中的有向邊也一一對應.我們把這樣的圖模型稱為軟件生態圖.

定義3.軟件生態圖.它是一張表示軟件生態中的應用軟件及其之間依賴關系的有向圖.圖中的每個點對應生態中的一個應用軟件，每條邊對應一個依賴關系，邊的方向規定為：應用A依賴應用B，對應從A指向B的邊.

在軟件生態圖中，我們把被兼容的應用稱為兼容點，不被兼容的應用稱為不兼容點，同理也有直接兼容點和直接不兼容點.我們提出定義2 在軟件生態圖模型下的一個等價定義，并證明其等價性.

定義4.軟件生態圖中的不兼容點.它是那些可通過圖中的路徑到達直接不兼容點的結點（路徑長度可以為0），即

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

定義4與定義2 的等價性證明為：

1）對于可通過一條路徑到達直接不兼容點的點，如果這條路徑長度為0，則該點是直接不兼容點，當然也是不兼容點；否則，可以將該點記為a，路徑記為（a,an,an-1, …,a1,a0），n≥0，a0是直接不兼容點.根據定義2，a0是不兼容點，a1因為依賴了不兼容點a0，也是不兼容點.反復進行推理可知，a1, …,an-1,an,a都是不兼容點.

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

根據定義4，只要遍歷某個應用結點的所有無環路徑，就可以判定該應用是否被兼容.

3.5 應用軟件生態兼容分析結果

表5 展示了openEuler 的4 種軟件生態的musl libc 兼容情況，其中第n級不兼容數的含義為在第n輪傳遞后新增加的不兼容應用個數，兼容率為被兼容的應用個數占全部應用個數的比例.

Table 5 Statistics of Compatible Applications in the Four Ecosystems表5 4 種生態中的兼容的應用軟件統計

比較表5 中數據發現，C 庫在相同應用場景（服務器或嵌入式）、不同體系結構下有著相近的直接兼容率和不兼容傳遞模式，而在相同體系結構、不同應用場景下數據的差異很大：服務器場景中兼容率分別為31.89%和31.87%，其各級不兼容傳遞的應用個數分別為537/547，6 936/6 985，4 721/4 727，198/190，7/10；嵌入式場景中兼容率分別為45.24%和44.58%，其各級不兼容傳遞的應用個數分別為33/33，13/13.而在不同應用場景下，兼容率的差值分別為13.35%（aarch64）和12.71%（x86_64），不兼容傳遞模式也有明顯區別.

這表明，軟件生態兼容情況受應用場景的影響很明顯，而受硬件體系結構的影響很微弱.

4 兼容性算法

兼容性的度量是許多系統開發者的需求，而好的度量方法是獲得優質度量結果的關鍵所在.

3.5 節中提到的兼容率是一種樸素的度量方法，它基于一個簡單的數學原理——計數.每個應用軟件都在計數時被同等地視作“1”，兼容應用的個數和所有應用的個數的比值就是度量結果.因此，兼容率不能體現不同應用軟件之間的差別.

應用軟件在生態中的重要性并不等同，這種差異體現在：

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

2）應用軟件開發者的角度.應用軟件開發者大多選擇以那些已經廣泛支持其他應用的應用為基礎，開發自己的應用軟件，因為基礎應用的功能豐富，正確性和安全性得到廣泛的實踐驗證，一般能得到持續穩定的維護，從而使得開發工作更加便捷、產品穩定性更佳、產品便于和其他應用互通或適配，等等.這些優勢使得開發者的產品更受用戶青睞，而這又促使更多開發者在這些基礎應用之上開展工作，形成以基礎應用為中心、其他應用對其依賴的生態結構，這是應用重要性差異的又一體現.

本節基于3.4 節中的軟件生態圖模型，提出了利用PackageRank 算法計算應用軟件的重要性和C 庫的兼容性，以在兼容性度量時體現重要性差異.

4.1 影響應用軟件重要性的因素

應用軟件之間的依賴關系能反映其重要性差異.不論是從系統用戶還是應用軟件開發者的角度，依賴關系都和應用軟件重要性有著緊密的聯系.

被大量應用軟件依賴的應用軟件相對更加重要.然而，把被依賴次數當作應用軟件的重要性也有失偏頗，如某個“只被一個很重要的應用依賴”的應用可能比“被多個很不重要的應用依賴”的應用更重要，因為它事關生態中的重要應用軟件的正常運行.

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

1）被其他應用依賴的次數；

2）依賴它的應用的重要性.

4.2 PackageRank 算法

PackageRank 算法是本文提出的兼容性度量算法.該算法分為2 個部分：計算應用軟件的重要性、計算C 庫的兼容性.

4.2.1 計算應用軟件的重要性

PackageRank 算法同時考慮了4.1 節所述的影響應用軟件重要性的2 種因素.它的思想基于Page 等人[21]提出的PageRank 算法，即PageRank 算法應用于代表互聯網的有向圖中，而PackageRank 算法則是將其應用到軟件生態圖.

圖3 展示了經過簡化的PackageRank 算法，它是一個迭代過程：每個結點將它現有的得分沿所有“出邊”平均分發，并將所有“入邊”的得分求和，作為新一輪迭代之前的得分.本文將PackageRank 算法經過多次迭代得到的穩定結果作為應用軟件的重要性度量值.

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

Package Rank 算法的含義是：

1）“入邊得分求和”使得被更多應用依賴的應用因為有更多得分來源而獲得更高得分；

2）“出邊平均分發”使得被更高得分的應用依賴的應用能獲得更高得分.

由此可見，PackageRank 算法兼顧了影響應用軟件重要性的2 個因素.

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

1）排序沉沒.軟件生態圖中可能存在環，即應用之間可以環形依賴.當環中的全部應用都被兼容時，它們都能正確運行，否則便都不能正確運行.如果存在指向環中某個點的邊，所有的點又均沒有指向環外其他點的邊，則得分可以進入環但不能排出，從而在環中無限積累，如圖4 所示.可能存在1 個或多個這樣的環，而不在這些環內的點最終都將沒有得分.

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

2）懸鏈接.有些應用不依賴任何其他應用，即它對應的點在軟件生態圖中沒有出邊.在迭代過程中，賦予這些點的分數將從圖中泄漏，如圖5 所示.

為了解決排序沉沒和懸鏈接，算法在每次迭代后令每個結點都“流失”一定比例的得分，同時向所有結點補充分配分數以維持總得分恒定.其中，得分流失和補充使得所有得分不會全部流入閉環中，而得分補充還可以補足因懸鏈接而泄漏的得分.

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

定義5.應用軟件的重要性.重要性度量結果為向量R，滿足：

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

可以根據軟件生態圖構造矩陣An×n（n是生態中應用的個數）：將所有應用軟件編號為1～n.對于1≤i≤n和1≤j≤n，如果應用i被應用j依賴，則Aij= 1 /Nj，Nj是應用j依賴的應用個數（點j的出度）；否則Aij=0.算法收斂后的向量R（第i維上的值是應用i的得分）滿足R=AR.An×n稱為依賴關系矩陣.

算法1 展示了PackageRank 計算應用軟件重要性的過程.

算法1.PackageRank 計算應用軟件重要性R.

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

流失因子ε的大小會影響算法的計算結果.如果ε過大，依賴關系網在算法中的作用將被減弱，導致結果不準確；如果過小，算法收斂速度更慢.Page 等人[21]建議ε=0.15，以表征網絡用戶隨機跳轉訪問網頁的概率；而由于ε在此處僅為避免排序沉沒，選取的值太大將帶來較大誤差，故本文設定ε=0.001.重新補充分配得分的方法是平均分配，這是因為open Euler 缺乏其他與應用軟件相關的統計數據或信息.

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

Fig.6 Importance of applications computed by PackageRank圖6 PackageRank 計算的應用軟件重要性

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

這一軟件生態的特點符合自然界生態系統的規律.少數食物鏈頂端的物種能得到大量的能量輸入，在系統中也更具支配性；而底端的低級生物只能靠更多的數量來維持平衡.軟件生態和自然界生態系統的發展過程有所相似，依賴關系網和食物鏈網也是類似的結構，而PackageRank 的結果也正是自然界的生態規律在軟件生態中的延伸，這體現了算法的合理性.此外，嵌入式生態中的得分分布更為均衡的原因則是其生態規模更小、復雜度更低，重要的應用不能積累足夠的分數而與其他應用拉開差距.

4.2.2 計算C 庫的兼容性

兼容性的度量方法應當體現應用軟件重要性的差異.C 庫兼容更重要的應用軟件，對生態的積極作用更顯著，C 庫的兼容性便得到更大幅度的提升；C庫不兼容重要應用，對生態造成的破壞也更大，兼容性將受到更大的影響.因此，通過對被兼容應用的重要性評價（PackageRank 得分）來計算兼容性是十分合適的.

雖然PackageRank 為每個應用軟件輸出一個確定的得分，但如果將所有應用軟件的得分縮放同樣的比例，得到的結果仍是穩定的.通過改變定義5 中‖R‖1的值，就能實現得分的縮放.因此，得分的比值更具意義，它反映的是生態中各個應用的“相對重要性”.這個屬性是應用軟件生態的固有屬性，與得分的縮放無關.我們采用所有被兼容應用的重要性得分之和與全部應用得分之和的比值來度量C 庫的兼容性.由于‖R‖1=1，故只需將所有被兼容應用的得分求和便能得到這個比值.

定義6.C 庫在軟件生態內的兼容性.兼容性定義為所有被兼容應用的重要性得分之和與全部應用得分之和的比值，即為所有被兼容應用的得分之和.

表6 展示了musl libc 在openEuler 的4 種生態中的兼容性度量結果.

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

不同應用場景的兼容性差別很大，而體系結構對兼容性的影響很小.嵌入式生態的C 庫兼容性較服務器生態高出26%左右，而實際情況也確實如此，即嵌入式生態的應用多為主流應用，它們更多地調用常用的API，而缺失API 普遍是不常用且功能特殊的，因此應用軟件調用缺失API 的概率更低.

至此，我們發現musl libc 對應用軟件的兼容性仍有很大的提升空間，在替換前需要進一步補全開發工作.

5 缺失API 優先級算法

C 庫的開發者不僅需要了解C 庫的兼容性，而且更需要獲知缺失API 的優先級，以便按序進行補全.

缺失API 的優先級差異體現在兼容性價值上：C庫通過補全API 而兼容更多應用軟件運行，不同API被應用軟件調用的情況有差別，應用軟件的重要性又有差別，從而補全不同的API 對生態的兼容性價值也有高低之分.

本節提出了有接口的軟件生態圖模型，并在該模型上提出了APIRank 算法以度量缺失API 優先級，然后按照優先級次序進行了API 補全模擬.

5.1 影響缺失API 優先級的因素

與4.1 節類似，缺失API 的優先級也受多重因素的影響.被大量應用軟件調用的缺失API 應優先實現，以滿足眾多應用的功能需求；重要的應用軟件調用的缺失API 應優先實現，以保證重要應用的正常運行.此外，如果一個應用軟件調用的缺失API 數量過多，要兼容該應用就需要大量的工作，兼容性提升效率降低，且開發過程不易調試[21]，故這些API 的優先級降低.因此，缺失API 的優先級受3 種因素的影響：

1）調用它的應用軟件的數量；

2）調用它的應用軟件的重要性；

3）調用它的應用軟件所調用的缺失API 總數.

5.2 APIRank 算法

為綜合考慮5.1 節所述的3 個因素，我們基于軟件生態圖和PackageRank 算法作進一步延伸，提出了有接口的軟件生態圖模型和APIRank 算法以度量缺失API 的優先級.

在軟件生態圖中，應用軟件之間的依賴關系對應著圖中的有向邊.這種將依賴關系模型化的思路在有接口的軟件生態圖中得到了延續.應用軟件對API 的調用可以被視作一種廣義的“依賴”關系.應用軟件“依賴”API，正如應用軟件依賴其他應用一樣.依照這個思路，可以構造一張由應用軟件和缺失API 共同組成的有向圖，并根據廣義依賴關系在圖中連接對應的邊.我們把這樣的有向圖稱為有接口的軟件生態圖.

定義7.有接口的軟件生態圖.它是一張表示軟件生態中應用軟件和缺失API 及其之間廣義依賴關系的有向圖.圖中的每個點對應生態中的一個應用軟件或一個缺失API，每條邊對應一個廣義依賴關系，邊的方向規定為：應用A依賴應用B，對應一條從A指向B的邊；應用C調用缺失APID，對應一條從C指向D的邊.

算法1 中的PackageRank 的計算過程同樣可以用于有接口的軟件生態圖，收斂后圖中每個結點也會有一個穩定的得分.本文將收斂后代表缺失API 的結點的得分視為缺失API 的優先級，這個算法稱為APIRank，如圖7 所示，它是圖4 添加了缺失的API 而生成的.

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

APIRank 算法的含義是：

1）被更多應用軟件調用的缺失API 有更多的分數來源，從而獲得更高的分數；

2）更重要的應用有更高的分數，它調用的缺失API 也能獲得更高的分數；

3）調用多個缺失API 的應用有更多的出邊，每個缺失API 能從出邊獲得的分數更低.

由此可見，APIRank 算法兼顧了影響接口優先級的3 個因素.

同樣地，可以根據有接口的軟件生態圖構造矩陣A（n+m）×（n+m）（n是應用個數，m是缺失API 個數）：所有應用編號為1～n，所有缺失API 編號為n+1～n+m.對于1≤i≤n+m和1≤j≤n+m，如果點j有指向點i的邊，則Aij= 1 /Nj，Nj是點j的出度；否則Aij= 0.A（n+m）×（n+m）稱為廣義依賴關系矩陣.

算法2 展示了APIRank 計算缺失API 優先級的過程.

算法2.APIRank 計算缺失API 優先級.

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

根據缺失API 的得分R的高低，可以對其優先級進行排序.

5.3 接口補全模擬

我們模擬了按照缺失API 優先級排序進行補全時，musl libc 兼容性隨著每個API 的補全而逐步提升的過程，如圖8 所示.

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

圖8 的結果顯示，musl libc 兼容性的提升呈階梯型，這是因為在開發過程中往往需要實現多個API才能兼容某一個應用軟件，而該應用軟件的兼容能夠（或許會大幅度地）提升C 庫的兼容性.同一應用場景、不同體系結構的兼容性提升過程相似，而不同應用場景的過程區別較大，這也完全符合我們的預期.

注意到，當C 庫達到完全兼容（兼容性為100%）時，并非所有的缺失API 均已被補全，即代表完全兼容的點的橫坐標值均小于表2 中的主要接口缺失總數（1 379）.這表明有些缺失API 未被生態中的任何應用軟件調用.根據本文對兼容的定義，這些缺失API 沒有對應用軟件生態提供任何有效的兼容支持，目前并不需要補全它們就能達到完全兼容，它們也不包含在有接口的軟件生態圖中，從而不存在APIRank 算法得分（無優先級）.

圖9 展示了被調用和未被調用的缺失API 數量和占比.我們發現未被調用的API 所占的比例很高：嵌入式生態中有95.9%的缺失接口未被應用軟件調用過；服務器生態中，aarch64 和x86_64 的數據分別是85.3%和85.1%.API 未被任何應用軟件調用，一般是因為其功能過于特殊而缺乏實用場景，或存在與其功能類似但更受應用開發者喜愛（性能更好，更符合編程習慣等原因）的其他API.嵌入式生態的比例比服務器生態低10%，而這也和嵌入式生態的兼容性更高（見表6）相呼應.

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

openEuler 的C 庫開發者當前無需擔心這些未被調用的API 會帶來兼容性問題.而且，目前未被調用的API 短期內也很可能不會被應用軟件的開發者使用，因此C 庫開發者有較長的時間來逐一補全它們（如果需要），同時該C 庫又能不受影響地提供服務.

6 評 估

本節評估了PackageRank 算法和APIRank 算法的效果，分析算法誤差，對比其他現有算法，展望算法的延伸，以及闡明本文研究的局限.

6.1 算法效果

6.1.1 PackageRank 算法效果

PackageRank 算法的評估采用aarch64 體系結構的結果作為例子.表7 給出了在aarch64 的2 種應用場景下PackageRank 得分排名較高的應用的分值.為了更清晰地顯示結果，表7 中的得分是經過等比例放大的，這樣的放大并不影響算法結果的穩定和準確.

Table 7 Statistics of High-ranked Applications of PackageRank in aarch64表7 aarch64 體系結構下PackageRank 高優先級應用的統計

PackageRank 考慮了影響應用軟件重要性的2 個因素：被依賴次數、依賴應用的重要性.由表7 可知，這2 個因素實際都對結果產生了影響.服務器生態中，bash，texlive-base 都既被大量應用依賴（入邊數很高），又被高分應用依賴并獲得了大量得分（最大入邊分數高，最大入邊分數來源的分數和排名高）；texlivekpathsea 是典型的僅因大量應用依賴而積累出高分的例子，有3 190 個依賴它的應用，但其中最高得分的應用也僅排名65；ncurses-base 則完全因為高分應用的依賴才成為了排名第3 的應用，它只有2 個依賴者，而其中ncurse-libs 為它輸送了96.9%（3 487.70/3 598.00）的高額分數.嵌入式生態中，bash 受2 種因素影響而排名第1，zlib，libselinux 主要因為被依賴次數高，而libsepol 則主要因為從libselinux（排名第4）處獲得大量分數而排在第3 位.

此外，服務器生態中的perl-libs 和perl-Exporter存在雙向依賴，這是排序沉沒問題出現的例子，在算法中已經解決了這個問題（4.2 節）.

應當指出，平均入邊分數與入邊數的乘積并不等于得分，而是約等于得分減1（存在微小誤差）.這是因為PackageRank 在迭代時對每個點進行了等額的得分補充（4.2 節）.補充的得分并不來自入邊，而表7 中的得分就是將這部分補充的得分縮放為1.00后的結果.

上述分析表明PackageRank 算法有效地實現了對應用軟件重要性的多重影響因素的兼顧.

6.1.2 APIRank 算法效果

APIRank 算法的評估采用x86_64 體系結構的結果作為例子.表8 列出了在x86_64 的2 種應用場景下APIRank 算法中優先級較高的API 的分值.

Table 8 Statistics of High-ranked APIs of APIRank in x86_64表8 x86_64 體系結構下APIRank 高優先級API 的統計

服務器生態中，應用軟件的高分對其所調用的缺失API 的優先級提升作用明顯：PackageRank 中排名第1 的coreutils 調用了6 個缺失API，它們均排在前7 名中.另一方面，被大量應用軟件調用也能提升API 優先級，fcntl64 有遠超其他API 的被調用數（入邊數），這也使得它排在第2 名.另外一個例子則能體現這2 個因素對優先級的共同影響：dlvsym 和argz_add 得分接近，但分別主要受被調用數和調用者重要性的因素影響，表明在不同主要因素影響下缺失API 也能得到相近的分數.

嵌入式生態結構比較簡單，且其應用軟件調用的缺失API 數量更少，因此API 優先級得分比較接近，但仍能看出多個因素共同影響優先級的效果.特別地，mallinfo 和obstack_vprintf 的得分接近，前者的被調用數和調用者最高得分都更高（3 對1，3.26 對1.00），但其調用者（e2fsprogs）所調用的總缺失API 數更多（4 個，另外1 條出邊是應用依賴關系），故其得分與后者接近，這體現了第3 個因素對結果的影響.

上述分析表明APIRank 算法有效地實現了對缺失API 優先級的多重影響因素的兼顧.

6.2 算法誤差

本文算法的誤差有2 個來源：

1）流失因子ε和得分補充.本文中ε=0.001，得分補充方法為平均分配，因此在每輪迭代后有0.1%的分數從各個結點中流失，并平均分配到所有結點.因此，兼容性誤差在0.1%以內；缺失API 優先級的數值存在誤差，但排序不存在誤差，即按比例流失和平均分配不影響得分之間的大小關系.

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

綜上，兼容性誤差在0.1%以內，缺失API 優先級的平均誤差在10-7以內.由于在4 種生態內的所有缺失API 的優先級得分均高于10-5，故APIRank 的平均誤差低于1%.

6.3 算法對比

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

1）算法A：已實現的API 個數；

2）算法B：文獻[2]的加權完整性.

算法A的度量方式因缺乏應用軟件所包含的信息而不準確，在本節中不再討論.

算法B是將其他系統與Ubuntu 15.04 作比較，或模擬將系統構件安裝在Ubuntu 15.04 上并研究其兼容性.之所以選擇Ubuntu 15.04 為基準系統，是因為它是“管理良好的、廣泛支持應用軟件的、統計軟件包安裝數據的Linux 發行版”.文獻[2]統計API 調用情況時使用Ubuntu 的RPM 包，API 重要性和加權完整性的計算也均采用Ubuntu 的安裝次數統計.

我們認為算法B不適用于openEuler 對musl libc兼容性分析的原因是：

1）openEuler 的應用軟件生態與Ubuntu 有區別，RPM 包的內容也有所不同；

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

3）應用軟件的安裝并非獨立事件，而是存在互相依賴關系.

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

對比其他算法，本文提出的PackageRank 算法的優勢和特點在于：

1）為系統提供從自身應用軟件生態出發的、個性化的兼容性評估.不同系統能夠搭載的應用軟件范圍（即生態）不同（Ubuntu/Debian 生態中有30 976 個應用[2]，openEuler x86_64 服務器生態有18 288 個，open-Euler x86_64 嵌入式生態有83 個），很難為多種多樣的系統確定統一的“基準生態”.本文的算法以每種系統或構件各自的應用軟件生態信息作為輸入，反映API 在其真實應用場景的兼容性，為開發者提供準確的、個性化的評估結果.

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

APIRank 的優勢和特點除包含前述內容外還有：面向仍有開發需求的系統和構件，為API 的補全實現工作提供幫助.現有研究大多面向已經完整實現的系統和構件，分析已有API，而本文的算法僅度量缺失API 的優先級，為仍需開發的系統和構件提供補全順序的建議.本文算法并非為Linux API 的全局現狀和生態環境做分析，而是為系統和構件開發者提供方案建議.

6.4 展 望

1）目前并沒有將PackageRank 和APIRank 應用于完整開發過程的例子，但openEuler 已經開始按照APIRank 計算出的優先級順序開展補全工作.在開發過程中發現，有些高優先級API 并非在musl libc 中實現，而是以別名實現（如error）或在其他分支庫中實現（如backtrace），這表明高優先級API 在musl libc 的開發者看來也十分重要，因此他們沒有拒絕實現這些API，只是其實現細節與glibc 存在區別.APIRank的分析結果和musl libc 開發者的觀點存在一致，有望為補全工作提供準確的信息和實質性的幫助.

2）在PackageRank 和APIRank 中，除應用軟件全集外，系統開發者還可以選擇將某個目標應用集作為研究對象，從而獲知系統或構件對該目標集的兼容性和缺失API 優先級.

3）PackageRank 和APIRank 不針對某種特定系統或構件，因此它們有望適用于其他場景下的API兼容性分析，如其他C 庫、系統調用、向量化參數等.此外，還有望將它們應用于系統模擬器的兼容性度量.

6.5 局 限

1）有2 處假設存在不準確性：應用的可執行文件存在可鏈接API 的符號表條目，即視為API 被調用；API 存在即視為API 能正確工作.在3.1 節中，已經對它們的不準確性做出說明.

2）僅采用靜態分析而未考慮API 調用頻率等其他有關API 調用的信息，而靜態分析方法也無法準確給出這些信息.

3）沒有參考用戶對應用軟件的使用喜好和傾向，包括應用軟件之間的其他隱性關聯.

4）未全面考慮編譯環境和源碼對API 調用情況的影響，即應用軟件的開發者可能會通過宏命令，根據編譯環境的不同而調用不同的接口（特別是那些不在ANSI/ISO C 標準中的接口）.應用軟件的編譯環境會影響接口調用，接口缺失仍存在誤判.

5）實驗對象單一.本文的算法僅在openEuler 上的musl libc 兼容性研究中使用，未曾在其他系統或構件上開展工作.

7 結束語

本文研究了openEuler 的4 種軟件生態中的musl libc 兼容性和缺失API 優先級，以幫助openEuler 的C 庫開發者進行接口補全工作.

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

本文基于應用之間的依賴關系和應用對API 的調用關系進行兼容性和缺失API 優先級的度量.從依賴關系和調用關系到兼容性和優先級的轉化，是本文的核心思想和成果.

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