自動駕駛系統中多功能互動故障的自動修復
摘要在過去的幾年裡，已經提出了幾種自動修復策略來修復單個軟體程式中的錯誤，而無需任何人工干預。然而，很少有人研究自動化修復技術如何解決系統級故障，這些故障是由不同系統元件或功能之間的相互作用引起的。功能互動失敗在複雜系統中很常見，例如自動駕駛汽車，它通常由獨立的功能(即功能單元)組成。在本文中，我們提出了一種修復技術來自動解決自動駕駛系統中導致違反系統安全要求的不良特徵互動故障。我們的修復策略透過(1)定位程式碼的故障，(2)同時解決由獨立故障導致的多個互動故障，(3)將修復策略從單元級擴充套件到系統級，以及(4)根據故障的嚴重程度來解決故障。我們使用了包含四個功能的兩個自動駕駛系統來評估我們的方法。結果表明，我們的修復策略在不到 16 小時的時間內解決了這兩個系統中的互動故障，並且優於現有的自動修復技術。
1 引言自動駕駛系統軟體通常由幾個功能單元組成，稱為自動駕駛系統功能，用於自動執行特定的駕駛任務(例如，自動緊急制動、自動交通標誌識別和自動巡航控制)。每個功能隨時間連續執行，並從感知層元件接收資料。利用感測器提供的資訊，自動駕駛系統的功能獨立決定下一時刻汽車的運動。
不同功能做出的決定可能是衝突的。例如，自動巡航控制可以命令汽車加速以跟隨領頭汽車的速度，同時，自動交通標誌識別功能命令汽車停止，因為汽車正在接近具有即將變紅的交通燈的十字路口。為了解決衝突，自動駕駛系統應用了整合規則。整合規則本質上是條件語句，用於確定在什麼條件下應該優先考慮哪些功能的輸出。它們通常由工程師基於他們的領域知識手動定義，並被期望確保安全和期望的汽車操縱。
最近，在文獻中已經提出了許多方法來自動修復軟體程式碼中的錯誤。這些技術的輸入是一個有缺陷的程式和一個測試套件，測試套件包含一些期望的程式行為和一些揭示了需要修復的失敗的測試用例。故障修復技術反覆識別程式碼中的錯誤語句(故障定位)，自動修改錯誤語句(補丁生成)，並檢查補丁程式碼是否透過所有輸入測試用例(補丁驗證)。為了有效地修復 ADS 整合故障，我們需要一種技術，它除了支援上述三個步驟之外，還需要確保以下目標:
1、修復技術應該定位跨多行程式碼的故障。
大多數程式修復技術使用基於頻譜的技術來定位故障。這些技術依賴於程式中存在單個錯誤語句的假設，並且如皮爾遜等人所示，它們可能無法識別多語句錯誤中的所有錯誤行。正如我們在第 3 節中所描述的，整合規則中的錯誤通常是多位置的，因為它們可能跨越多行程式碼，例如，當規則以錯誤的順序應用時。
2、修復技術應該能夠修復程式碼中的多個獨立錯誤。
大多數程式修復技術假設給定(輸入)測試套件中所有失敗的測試用例都是由於程式碼中的相同錯誤而失敗的。因此，它們一次只能為一個故障生成一個補丁。生成的補丁可以替換單個程式語句，或者它們可以基於預定義的模板構建，規定硬編碼的變更模式來修改多個位置的程式。然而，對於 ADS 整合規則來說，程式碼中只有一個錯誤的假設是不成立的，因為測試用例可能會因為位於程式碼不同部分的多個錯誤而失敗。正如我們在第 3 節中所描述的，為了修復給定測試套件中所有失敗的測試用例，我們可能需要修復程式碼中的多處錯誤，例如，透過重新排序一些規則，另外，改變一些其他規則的前提條件。
3、修復技術應該擴充套件到在系統級修復故障。
測試 ADS 軟體需要一個基於模擬的測試平臺，該平臺可以針對不同的道路結構、天氣條件和交通狀況執行 ADS 軟體。使用模擬器測試 ADS 軟體面臨兩個挑戰：首先，每個測試用例是一個在一段時間內執行的場景，並透過反饋迴圈模擬執行 ADS 軟體。因此，單個測試用例是在每個模擬時間步長類執行 ADS 軟體，並隨著時間的推移生成一系列輸出，而不是單個輸出。因此，ADS 軟體中的依賴性既是結構性的(像典型的程式碼一樣)，也是臨時性的。其次，ADS 軟體的測試用例在計算上是昂貴的，因為每個測試用例必須執行一段時間，並且必須在每個時間步驟執行一個複雜的模擬器和 ADS 軟體。這限制了用於修復的測試套件的大小和我們可以生成的中間補丁的數量。
4、修復技術應該按照故障的嚴重程度來解決故障。
當測試軟體時，測試用例要麼透過，要麼失敗，並且沒有區分失敗的測試用例的因素。然而，對於 ADS 來說，有些失敗比其他失敗更關鍵。例如，違反速度限制 10 公里/小時的測試案例比違反速度限制 5 公里/小時的測試案例更關鍵。類似地，汽車以低於 10 公里/小時的速度撞上行人的測試場景相對於以更高的速度發生碰撞的測試場景相比，顯得不那麼重要。因此，我們的修復策略應該以更細緻的方式評估失敗的測試用例，並優先修復更關鍵的失敗測試用例，而不是不太關鍵的測試用例。
我們提出了一種自動修復自動駕駛系統整合規則的方法（ARIEL）。我們的修復策略依靠多目標、單一狀態搜尋演算法實現了上述的四個目標，該演算法使用存檔來跟蹤部分修復的解決方案。我們已經將 ARIEL 應用到我們合作公司的兩個自動駕駛系統案例研究中。結果表明，ARIEL 能夠在我們的兩個案例研究中平均在 5 小時和 11 小時內修復整合故障。我們報告了從工程師那裡收到的關於 ARIEL 實際用途的反饋。反饋表明，ARIEL 能夠生成整合故障的補丁，這些補丁是工程師可以理解的，並且，如果沒有任何自動化的工具，僅基於他們的專業知識和領域知識，他們無法開發這些補丁。
2 背景我們首先使用我們的行業合作伙伴的自動駕駛系統案例研究自動駕駛來啟發我們的工作。
圖 1:自動駕駛系統概述，由四個自動駕駛系統功能組成。
圖 2:解決不同 ADS 功能之間衝突的有序整合規則。
圖 1 顯示了自動駕駛的概述，包括四個自動駕駛系統功能:自動巡航控制（ACC）、交通標誌識別（TSR）、行人保護（PP）和自動緊急制動(AEB)。ACC 自動調整車速和方向，以保持與前車的安全距離。TSR 檢測交通標誌，並應用適當的制動、加速或轉向命令來遵守交通規則。PP 檢測汽車前方是否存在行人，並在需要時發出制動命令。AEB 防止與行人以外的物體發生事故。
圖 3:與圖 2 中的整合規則相關的決策樹圖的片段。
由於這些功能產生制動、加速和轉向命令來控制車輛，它們可能同時向汽車傳送衝突的命令。例如，ACC 命令汽車加速以跟隨領頭汽車的速度，而與此同時，行人開始橫穿馬路。因此，PP 開始發出制動命令，以避免撞到行人。
3 方法在這一節中，我們提出了我們的方法，自動化整合規則修復(Automated Require of IntegratIon RULEs，ARIEL)，以定位和修復整合規則中的錯誤。ARIEL 的輸入是(1)有故障的 ADS 和(2)驗證安全要求的測試套件。輸出是修復後的 ADS。下面，我們詳細介紹 ARIEL 的不同步驟。
3.1 錯誤定位功能互動失敗可能是由整合規則中的多個獨立錯誤引起的，其中一些錯誤可能跨越整合規則程式碼的多個語句。如先前的研究所示，最先進的故障定位方法通常不能精確定位所有的故障線路(即那些在程式修復中突變的線路)。此外，如第 1 節中所述，為了測試 ADS，我們必須在一段時間內以連續迴圈的方式執行系統。因此，每個 ADS 測試用例在模擬持續時間內將覆蓋多條路徑。
基於這些觀察，我們透過(1)關注故障時覆蓋的路徑，以及(2)考慮故障的“嚴重性”來修改錯誤定位公式。在本文中，我們將重點放在錯誤定位公式上，因為以前的一項研究表明，當應用於實際故障時，替代方法之間的差異可以忽略不計。下面，我們將描述我們如何修改錯誤定位公式來對故障路徑進行排序。
3.1.1 定位故障路徑給定一個由測試用例導致的失敗情況，我們的目標是確定更可能導致失敗的路徑。如上文所述，我們區分了兩種型別的故障:(1)錯誤的條件，即規則前提條件中的故障，例如，當汽車和行人之間的距離太小時，制動命令被啟用；以及(2)規則的錯誤排序，即由於規則啟用功能的錯誤排序而導致的故障。出於故障定位的目的，我們只考慮故障發生時執行的路徑，而忽略故障前後故障測試用例覆蓋的所有其他路徑。相比之下，在傳統的故障定位中，應該考慮測試用例覆蓋的所有語句(在我們的例子中是整合規則)。
3.1.2 失敗的嚴重性在錯誤定位公式(以及最先進的故障定位技術)中，所有失敗的測試在計算語句可疑度的公式中具有相同的權重。然而，在多個故障的情況下，這種策略無法優先修復其中的一些故障。關注與最嚴重的失敗相關的錯誤可以獲得在適應性方面具有最大潛在收益的補丁。我們可以衡量違反自動駕駛系統安全要求的嚴重程度。嚴重性對應於測試用例的輸出。對於測試用例和需求，輸出值越低，違反需求的嚴重程度越大。
#
3.2 程式修復傳統的修復工具，如 GenProg，使用基於種群的演算法(如遺傳演算法)，迭代地進化候選補丁池。針對整個測試套件評估每個候選補丁，以檢查更改是否會導致更多或更少的失敗測試。
基於群體的演算法假設評估單個補丁的成本不大，因此，可以在幾秒鐘內收集測試結果，並用於向搜尋提供反饋。然而，正如在第 1 節中所討論的，這個假設在我們的上下文中不成立，並且執行一個基於模擬的測試用例需要幾分鐘的時間。因此，在每次迭代/生成中評估一個補丁變得過於昂貴(幾個小時的數量級)。
演算法 1: ARIEL
基於以上觀察，我們選擇了帶有存檔的進化演算法。該演算法每代只選擇一個親本，只產生一個子代。一次只生成和評估一個補丁可以降低每次迭代的成本。我們的程式修復方法 ARIEL 包括(i) 進化演算法，(ii)我們的故障定位公式和(iii)存檔策略。演算法 1 提供了 ARIEL 的虛擬碼。
ARIEL 接收測試套件和具有故障的自動駕駛系統。輸出是一組經過修復的整合規則，這些規則通過了所有的測試用例。該演算法首先用錯誤的規則初始化檔案(第 2 行)，並計算目標分數，我們在下文(第 3 行)對此進行了描述。然後，檔案在第 4-8 行的迴圈中迭代演化。在每次迭代中，ARIEL 從檔案中隨機選擇一個補丁(第 5 行)，並透過(1)應用故障定位和(2)對規則進行變異，建立一個後代。
然後，透過執行測試套件，提取剩餘的故障，並計算它們相應的客觀分數，對子代進行評估(第 7 行)。請注意，故障的嚴重性是我們的搜尋目標，將在下文中進一步討論。如果子代與當前儲存在存檔中的補丁相比降低了故障的嚴重性，則新增到存檔中(演算法 1 的第 8 行)。存檔及其更新程式在下文中有詳細描述。當滿足終止標準時，搜尋停止。
3.2.1 生成補丁演算法 2: GENERATE-PATCH
ARIEL 使用演算法 2 中的程式生成補丁。首先，它應用我們的故障定位公式(第 2 行中的常規故障定位)來確定語句的可疑性。
為了從最可疑的語句中選擇一個語句，我們使用輪盤賭選擇(RWS)，它給每個語句分配一個被選擇突變的機率，機率基於每個陳述的可疑性。
3.2.2 存檔該存檔儲存搜尋過程中找到的最佳部分補丁。在搜尋開始時(演算法 1 的第 2 行)，用錯誤的規則集初始化存檔。每次建立和評估新補丁時，我們都會將其與儲存在存檔中的所有補丁進行比較。
因此，在每次迭代中，存檔將被更新(演算法 1 的第 8 行)，使得它包括迄今為止找到的最佳部分補丁。
儲存在存檔中的解決方案的數量可能會變得非常大。為了避免這種膨脹效應，我們為存檔檔案的最大大小增加了一個上限。在本文中，我們將檔案的大小設定為 2×k，其中 k 是安全需求的數量。如果存檔檔案的大小超過上限，則存檔檔案中的解決方案將根據聚合適合度值進行比較，然後，我們透過選擇適合度值最大的 2 × k 補丁來更新檔案。
進化演算法的一個可能的限制是它們會陷入區域性最優(早熟收斂)。處理這一潛在限制的一個成熟策略是重啟(重新初始化)搜尋。我們在 ARIEL 中實現了以下重啟策略:首先，ARIEL 使用一個計數器來計算在搜尋目標中沒有改進的後續代的數量(即，檔案永遠不會更新)。如果計數器達到 h 代的閾值，則透過刪除存檔中的所有部分補丁並使用原始故障規則集重新初始化它來重新開始搜尋。
3.2.3 終止標準當搜尋預算被消耗時，或者當找到了一個合適的補丁時，搜尋停止，即存檔包含一個滿足所有測試用例的補丁。這裡需要注意的是，即使我們的修復演算法是多目標的，它也只生成一個最終解。這是因為我們的演算法是單狀態搜尋，在每次迭代中只生成一個解。如果該解是最優的，則搜尋停止。
3.2.4 補丁最小化在搜尋結束時，ARIEL 返回一個合適的補丁(即它通過了所有測試)，但它可能包含為了修復虛假突變而產生的冗餘。這個問題可以透過補丁最小化演算法來解決，即迭代地移除一個突變並驗證反向改變後的補丁是否仍然透過測試套件的貪婪演算法。如果是這樣的話，就可以得到一個更小的(最小化的)補丁，這個補丁仍然可以透過測試。
4 結論我們提出了一種修復技術來自動化地解決自動駕駛系統中的整合故障。我們的方法將故障定位在多行程式碼上，以修復複雜的整合故障，並處理測試和修復自動駕駛系統的可伸縮性問題。我們的修復演算法依賴於多目標、單狀態搜尋演算法，該演算法使用存檔來跟蹤部分修復。我們的方法使用了兩個工業自動駕駛系統進行評估。結果表明，我們的修復策略可以修復這兩個系統中的整合故障，並優於現有的自動修復技術。來自領域專家的反饋表明，由我們的方法生成的補丁是工程師可以理解的，且如果沒有任何自動化工具的幫助，他們無法獨立開發出來。