藉由正規限制式之擬真運算處理符號檔案輸入

Abstract

軟體測試是軟體發展中一個重要的程序，而符號測試則是現今軟體測試中重要的技術之一。若符號測試範圍能涵蓋到檔案輸入的話，則我們將不需要修改程式碼來標記哪些變數有可能是符號變數，而可以透過標準輸入直接進行符號測試，符號測試將更為方便且全面。近年來，拜電腦的運算能力大幅提升及關於減少描述程式之限制式的改善方法不斷地被提出，符號測試涵蓋於檔案等級已經不再是難以達成的事情。在眾多的符號測試工具之中，KLEE 著眼於 LLVM(Low Level Virtual Machine) 所具備的中介語言對各程式語言及各硬體架構的良好獨立性，所以架構於 LLVM 之上來進行符號測試，是目前發展較為成熟且較受到矚目的符號測試工具之一。然而在 KLEE 中，由於符號檔案測試涵蓋了C語言標準函式庫，所以產生了過多的執行路徑，造成測試一個不到百行的小程式就得花上不少時間及記憶體，而所產的涵蓋新執行路徑的測試資料更是大部分只跟C語言標準函式庫的程式碼有關，只有一小部分是關於受測程式的新執行路徑。我們希望透過簡單的實作正規表示式限制符號檔案於 KLEE 之方式，專注於產生程式預期接收的測試輸入，以便在短時間內能更快的進入新的執行路徑。

Software testing is an important procedure of software development process, and symbolic testing is one of the most important techniques in the domain of software testing. If we can handle symbolic testing with file level, we can process testing directly via standard input rather than modifying source code and marking the symbolic variables. Nowadays, symbolic testing with symbolic files is feasible because of the powerful computing ability and the techniques about reducing constraints. In various symbolic testing tools, KLEE based on the top of LLVM(Low Level Virtual Machine) because that LLVM's assembly level instruction set is independent of programming languages and architectures. KLEE is one of well-developed and famous symbolic tools. However, KLEE does symbolic files testing still have some problems: symbolic files testing cover the C standard library and generate too many execution paths. The result is: (1) Waste a large amount of time and run out of memory when test a source code which is less than 100 lines. (2) The most ratio of test cases which can cover new paths relative testing source code to all test cases is too small. In other words, we spend too much time on generating new paths which cover C standard library. We want to improve the efficiency of generating execution paths by using regular expressions which describes a given format. In this way, we can explore useful execution paths which is covered the new part of source code in short period.