由執行軌跡逆向解析平行程式之執行行為

隨著科技日益精進的快速發展，處理器的個數及程式的計算複雜度也跟著提升，使得開發者及研究學者更難深入了解程式行為。對程式行為的深入瞭解有助於計算機結構設計、程式除錯和最佳化、通訊協議驗證和測試等相關領域之研究發展。程式行為涵蓋不同的面向，表達的方式形形色色，且往往視應用的需求而定，也因此偵測程式行為的方法也種類繁多。一種常用的方法是擷取程式執行軌跡來觀察其行為。程式執行軌跡包含程式行為的完整資訊，然而，困難點是如何自大量的軌跡資訊中推論出具有意義的結構和模式，並用具體的方式表述程式行為。若欲研究的對象為平行程式，則問題的困難度更高，因為平行程式的多執行緒會於執行期間產生非常複雜的交互作用，讓平行程式行為很難掌握並追蹤。在本碩士論文中，我們提出了一個新的方法，利用執行軌跡來推導平行程式的行為，並以軌跡衍生之有限狀態機 (TD-FSM)來表示。TD-FSM 不僅能以一種非常簡潔的方式展示整個程式的執行行為，也能夠有效的壓縮執行軌跡以降低檔案儲存大小和傳送時間。壓縮後的TD-FSM可以利用一個還原重現的機制，再重現一與原執行軌跡非常相似的重現軌跡，可應用於效能分析和平行程式最佳化等後續研究。最後，根據我們的實驗結果顯示，TD-FSM 相對於原始軌跡資訊可以有效減少99%的儲存空間，且仍然保存程式行為特性。

關鍵字

逆向工程；平行程式；執行軌跡

並列摘要

With the advance of technology, the growing number of processors and increasing computational complexity of programs have raised the degree of difficulty in fully understanding the behavior of the whole program. Such an understanding is invaluable for research such as computer architecture design, program debugging and optimizations, protocol verification and testing, etc. A viable solution to the problem is to extract the program execution traces to observe the program behavior. The challenge is how to deduce meaningful structures and patterns from the massive trace information to represent program behavior in a concrete way. Parallel programs make this even more difficult because of the complex interactions between the multiple threads of executions. It is thus necessary to develop more efficient solutions capturing the complicated parallel program behaviors from the massive and seemingly unstructured execution traces. This thesis presents a new approach to deducing the parallel program behavior by processing the program execution traces to derive a trace-derived finite state machine (TD-FSM). With TD-FSM, it is possible to show the program behavior in a very concise fashion. TD-FSM can also effectively compress the execution traces to reduce the trace size for ease of storage and transportation. If coupled with a replay method, it can further reproduce execution traces that are very similar to the original traces, for such applications as performance analysis and parallel program optimization. Our evaluations show that TD-FSM can reduce the trace size by 99%, achieving a compression rate compatible with popular compression algorithms and at the same time maintaining the program behavior.

並列關鍵字

Reverse Engineering ； Parallel Program ； Execution Trace

參考文獻

[1] N. Walkinshaw, R. Taylor, and J. Derrick, “Inferring extended finite state machine models from software executions”, in Reverse Engineering (WCRE), 2013 20th Working Conference on, Oct 2013, pp. 301–310.

[3] J. Antunes, N. Neves, and P. Verissimo, “Reverse engineering of protocols from network traces”, in Reverse Engineering (WCRE), 2011 18th Working Conference on, Oct 2011, pp. 169–178.

[6] Kai Koskimies and Erkki M ̈akinen, “Automatic synthesis of state machines from trace diagrams”, Softw. Pract. Exper., vol. 24, no. 7, pp. 643–658, July 1994.

[10] Katherine E. Isaacs, Peer-Timo Bremer, Ilir Jusufi, Todd Gamblin, Abhinav Bhatele, Martin Schulz, and Bernd Hamann, “Combing the communication hairball: Visualizing parallel execution traces using logical time”, IEEE Trans. Vis. Comput. Graph., vol. 20, no. 12, pp. 2349–2358, 2014.

[13] “The parsec benchmark”, http://parsec.cs.princeton.edu/.

國際替代計量

由執行軌跡逆向解析平行程式之執行行為

全文下載

主題瀏覽