近年來的軟體視覺化工具可以透過圖形來視覺化程式內部的資料以幫助程式設計師除錯，但它們在實用上還有許多限制，使得軟體視覺化工具無法普及並成為程式設計人員每天使用的工具之一。xDIVA(eXtreme Debugging Information Visualization Assistant)[1]是本實驗室所開發的視覺化除錯工具，可處理複雜多變的資料結構。xDIVA使用3D的圖形、顏色和動畫以盡可能地滿足除錯時視覺化的需求。
本論文包含兩個子主題：Graph Layout以及測試自動化。Graph是程式中常見的資料結構，而這方面的視覺化方法已經不少。其中最知名的graph視覺化陳列工具就屬AT&T實驗室所開發的Graphviz[2]。為了增強xDIVA之graph視覺化，本論文在xDIVA現有的陳列系統架構下，將 Graphviz 的陳列能力加入 xDIVA。而這個過程也用來檢驗xDIVA的陳列架構是否能夠輕鬆地移植陳列演算法。
另外，xDIVA經過多年的發展，在開發上常會因為一點修改而衍生其他錯誤，導致系統的不穩定。而運用人工重新執行所有測試案例不僅費時，也費力。這項工作一般稱之為迴歸測試。迴歸測試已經有許多商業化的工具可供選擇，但是商業化的工具除了價格可能太過昂貴之外，也必須面臨開發平台不被支援，甚至不適用特定應用(如本實驗室的xDIVA)。因此，本篇論文提出以侵入式測試為基礎的自動化迴歸測試。所謂侵入式測試指的是我們運用program instrumentation技術在xDIVA的原始程式碼中插入測試程式碼。在錄製測試案例的過程當中，透過程式碼取得必要的資訊並儲存。當重新執行時，由這些測試程式碼收集的資料與錄製的測試案例進行比對與驗證，以檢驗迴歸測試是否成功。

Software visualization tools nowadays can help programmers debugging by visualizing program data as graphics. Visualization tools in practice are limited because they are domain-specific or have fixed visualizations. xDIVA (eXtreme Debugging Information Visualization Assistant)[1] is a debugging visualization tool developed by our laboratory for handling the visualization for arbitrary data types. xDIVA uses 3D shapes, colors and animations to visualize data in a way that is not limited by the fixed visualization.
This thesis has two topics: graph layout and test automation. Graph is a commonly used data structure in computer programs. The visualization of graph already has fruitful research results. One of the popular graph visualization tools is Graphviz [2] developed by AT&T laboratory. In this thesis, we port Graphviz into xDIVA to enhance the capability of graph visualization in xDIVA. It is also a process to validate and improve whether xDIVA layout framework allows layout algorithms to add in an easy manner.
Besides, xDIVA has developed for years. Sometimes a bug fix produces other bugs. It is necessary to execute all the test cases manually, albeit time-consuming. This process is known as regression testing and should by automated. Commercial test automation tools for regression testing are prevalent, but they can be expensive. However, these commercial tools are not suitable for the test automation of xDIVA. In this thesis, we produce an in-house test automation tool, which is intrusive because additional code needs to be inserted into source code as probing points. When xDIVA executes, the probing points record and collect program runtime information to verify the correctness of the test cases.

[1] Y. –P. Cheng, J. –F. Chen, M. –C. Chiu, N. –W. Lai, and C. –C. Tseng, “xDIVA: A debugging visualization system with composable visualization metaphors” in Proc. ACM SIGPLAN International Conf. OOPSLA’08, Nashville, TN, USA. 2008
[2] J. Ellson, E. Gansner, E. Koutsofios, S. North, and G. Woodhull, ”Graphviz and Dynagraph – Static and Dynamic Graph Drawing Tools”, Graph Drawing Software, Springer Verlag, 2003.
[3] G. Booch, J. Rumbaugh, and I. Jacobson, The Unified Modeling Language user guide, 1st ed. Addison-Wesley, 1997
[4] S. Reiss, “An overview of BLOOM.” In Proc. ACM SIGSOFT-SIGPLAN workshop. PASTE’01, pp. 2–5, Snowbird, Utah, 2001
[5] L. Michele, D. Stéphane, G. Harald, P. Martin, “CodeCrawler: an information visualization tool for program comprehension”, in Proc. ACM-SIGSOFT International Conf. 27th ICSE, pp.672-673, St. Louis, MO, USA, 2005
[6] N. E. Fenton and S. L. Pfleeger, “Software Metrics: A Rigorous and Practical Approach”, 2nd ed. Brooks-Cole, 1997.
[7] M. Fewster, and D. Graham, Software Test Automation: Effective Use of Test Execution Tools. 1st ed. Reading, MA: Addison-Wesley. 1999
[8] T.-H. Chang, T. Yeh, and R. C. Miller, "GUI testing using computer vision," in the Proc. of the 28th international conference on Human factors in computing systems, pp.1535-1544, Atlanta, Georgia, USA, 2010.
[9] HP QuickTest Professional. (n.d.). Retrieved June 12, 2010, from http://en.wikipedia.org/wiki/HP_QuickTest_Professional
[10] Rational Functional Tester. (n.d.). Retrieved June 13, 2010, from http://www-01.ibm.com/software/awdtools/tester/functional/
[11] T. Panas, R. Lincke, and W. Löwe. “Online-configuration of software visualization with Vizz3D”. In Proc. of ACM Symposium on Software Visualization (SOFTVIS’05), pp. 173–182, St. Louis, MO, USA, 2005.
[12] S. P. Reiss , M. Renieris, “Demonstration of JIVE and JOVE: Java as it happens,” in Proc. of the ACM-SIGSOFT International Conf. 27th ICSE, pp.662-663, St. Louis, MO, USA, 2005
[13] W. D. Pauw, E. Jensen, N. Mitchell, G. Sevitsky, J. Vlissides, and J. Yang, “Visualizing the Execution of Java Programs,” in Proc. International Seminar on Software Visualization(SOFTVIS’02), pp. 151-162, Dagstuhl Castle, Wadern,2002
[14] A. Zeller, and D. Lütkehaus. “DDD—A free graphical front-end for UNIX debuggers”. In Proc. of the ACM SIGPLAN Notices, pp. 22–27, New York, NY, USA, 1996
[15] J. Heer , S. K. Card , J. A. Landay, ”prefuse: a toolkit for interactive information visualization”, In Proc. of the SIGCHI conference on Human factors in computing systems, pp. 421-430, Portland, Oregon, USA, 2005
[16] J. v. Pilgrim and K. Duske, “Gef3D: a framework for two-, two-and-a-half-, and three-dimensional graphical editors.” in Proc. of the 4th ACM symposium on Software visualization (SoftVis’08), pp.95-104, New York, NY, USA, 2008
[17] G. Junker, Pro OGRE 3D Programming. 1st ed. APress, 2006
[18] P. Tahchiev, F. Leme, V. Massol, and G. Gregory, JUnit in Action. 2nd ed. Manning Publications, 2010
[19] HP WinRunner. (n.d.). Retrieved June 10, 2010, http://en.wikipedia.org/wiki/HP_WinRunner
[20] E. Gansner, E. Koutsofois, and S. North. (2006) Drawing Graphs with Dot. [pdf] Available: http://www.graphviz.org/Documentation/dotguide.pdf.
[21] T. Biedl, J. Marks, K. Ryall, and S. Whitesides. Graph multidrawing: Finding nice drawings without defining nice. In GD '98, volume 1547 of LNCS, pages 347–355. Springer-Verlag, 1998.
[22] Tyson R. Henry , Scott E. Hudson, “Interactive graph layout”, Proceedings of the 4th annual ACM symposium on User interface software and technology, p.55-64, November 11-13, 1991, Hilton Head, South Carolina, United States
[23] D. P. Dobkin, A. Hausner, E. R. Gansner, and S. C. North, “Uncluttering Force-Directed Graph Layouts,” Proceedings of the Fifteenth Annual Symposium on Computational Geometry, pp. 425-426, 1999.
[24] T. Masui. “Evolutionary learning of graph layout constraints from examples.” In Proceedings of the ACM Symposium on User Interface Software and Technology, Demonstrational User Interfaces, pages 103–108, 1994.
[25] J. Díaz , J. Petit , M. Serna, A survey of graph layout problems, ACM Computing Surveys (CSUR), v.34 n.3, p.313-356, September 2002
[26] E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995