臺灣博碩士論文加值系統

軟體剽竊是使用未授權軟體或散播版權軟體，軟體剽竊的比例和金額到現在為止仍然是非常高的。軟體保護技術是用來對抗軟體剽竊，軟體保護技術是在偵測到不希望或惡意的修改後，可以不啟動原有程式的一些或整個的功能，來達到軟體保護的目的。已經有許多的軟體保護技術，包括混淆(obfuscation)、防篡改、軟體浮水印、密碼學等。因為Java反編譯器(decompiler)的出現，使得Java程式容易被反編譯和反向工程(reverse engineering)，所以，未被保護的Java程式很容易被竊取，我們主要的研究是使用混淆、防篡改、軟體浮水印等技術來保護Java程式。
本論文提出一些保護Java軟體的新穎的混淆、防篡改和軟體浮水印技術。本研究整合了不明顯的雜湊運算(oblivious hashing)、保護網(guards network)與複雜流程混淆法(control flow obfuscation)等三種軟體保護技術，發展了同一系列共四種方法以保護Java程式。
混淆是透過ㄧ些容易讓反編譯器混淆的方式，讓程式中要傳達的意義或程式碼被隱藏起來，使程式難以被解析，並且使Java 程式免於被反編譯的威脅。我們設計了三種新的控制流程混淆的方法保護Java類別檔，包括了基本區塊分裂混淆法、迴圈交叉混淆法、取代goto混淆法，同時也建置多階層離開混淆法和單一階層離開混淆法以做比較。
防篡改技術則是使得惡意主機(人)對程式或資料的竄改失效，以保護軟體。首先，我們提出新的動態堆疊追蹤法改良不明顯的雜湊運算，使其適用在Java程式，並在程式中加入額外的雜湊指令監控堆疊的頂層元素，藉此判別程式的資料是否曾被篡改。接著，繼續研究加強使用新的不明顯的雜湊運算，引入保護網(guards network)的概念，並找出程式片段的支配樹（dominator tree），組成嚴密的檢查網，增加對程式資料的保護強度，最後將其隨機轉換成三種複雜的程式流程混淆法，保護程式防止被反編譯。
軟體浮水印是經由隱藏一些安全資訊在程式中，可辨別所有者的版權資訊，並保護軟體的所有權。我們使用混淆和防篡改技術，發展強健的軟體浮水印技術，以防止被破解。
綜言之，本研究成功的整合了不明顯的雜湊運算、保護網與複雜流程混淆法等三種軟體保護技術，完成了混淆、防竄改和軟體浮水印等四種方法，以保護Java程式防止被竊取。

Software piracy is the unauthorized copying or distribution of copyrighted software. The money loss for software piracy is still very high in this world now. Software protection is used to against software piracy. Software protection techniques disable part or all the functions of a program upon detecting any unwanted modifications. There are many software protection techniques, such as obfuscation, tamper-proofing, software watermarking, cryptography, etc. Java programs can be easily decompiled and reverse engineered from Java bytecode to Java source code by decompilers. So, Java programs are prone to be pirated.
Our studies focus on software protection techniques for Java programs. The major contributions are that we develop four methods to protect Java programs by obfuscation, tamper-proofing and software watermarking technologies.
Obfuscation is to transfer a source code into a form that is not easy to understand for decompilers. We develop three novel control flow obfuscation methods for protecting Java class files. They are basic block fission obfuscation, intersecting loop obfuscation, and replacing goto obfuscation. Multi-level exit obfuscation and single-level exit obfuscation are also implemented for comparison.
Tamper-proofing techniques will disable some or all of the program functionality once they detect any unwanted modifications during run time. First, we propose a tamper-proofing software technology on basis paths for stack-machine based languages, such as Java, by improving oblivious hashing. Our approach is based on a new dynamic stack-tracing approach which inserts hash instructions to monitor the top of the stack to check whether the running program has been tampered with or not. Second, we propose an approach to robustly protect the data of a dominant path in a method of a Java bytecode program by integrating oblivious hashing, guards network, and control flow obfuscation. A dominator tree based on the basic blocks of the target method is first built. Then the dominant path of the dominator tree is selected. The bytecodes of the dominant path are then transformed by the oblivious hashing, guards network, and control flow obfuscation.
Software watermarking protects software through embedding some secret information into software as an identifier of the ownership of copyright for this software. We use the propose obfuscation and tamper-proofing techniques to make software watermarks hard to find and to protect the program(s).
In summary, this dissertation presents obfuscation, tamper-proofing and software watermarking technologies to protect Java bytecode programs based on our enhanced oblivious hashing, guards network, and control flow obfuscation and to reach the goal to protect Java programs.

摘要 III
ABSTRACT IV
ACKNOWLEDGEMENT 致謝 VI
LIST OF FIGURES X
LIST OF TABLES XII
CHAPTER 1 INTRODUCTION 1
1.1 Software Reverse Engineering 1
1.2 Threats and defenses of Java Programs 1
1.2.1 Obfuscation 4
1.2.2 Software watermarking 5
1.2.3 Tamper-proofing 6
1.3 Summary 6
CHAPTER 2 BACKGROUND 8
2.1 Obfuscation 8
2.2 Tamper-proofing 11
2.3 Software Watermarking 13
2.4 Summary 14
CHAPTER 3 THREE CONTROL FLOW OBFUSCATION METHODS 15
3.1 Basic Block Fission Obfuscation 15
3.2 Intersecting Loop Obfuscation 18
3.3 Replacing Goto Obfuscation 20
3.4 Testing Results 22
3.5 Summary 23
CHAPTER 4 TAMPER-PROOFING BASIS PATH USING OBLIVIOUS HASHING 24
4.1 Java Oblivious Hashing 24
4.1.1 The Abstract Model 24
4.1.2 Oblivious Hashing for Java Software 25
4.1.3 The Concept and Examples of Oblivious Hashing 26
4.1.4 Eliminate the Influence of Variables 28
4.2 Tamper-proofing the Basis Path 32
4.2.1 Tamper-proofing to intermix the Basis Path 33
4.3 Implementation of Java Oblivious Hashing 34
4.3.1 Performance Analysis 34
4.3.2 Tamper-proofing Basis Path Using Oblivious Hashing 35
4.3.3 Discussion 37
4.4 Summary 37
CHAPTER 5 TOWARD ROBUSTLY PROTECTING DATA OF A DOMINANT PATH IN A JAVA METHOD 38
5.1 The Propose Approach 38
5.1.1 Java Oblivious Hashing and Guards Network 39
5.1.2 Guards Network and Dominant Path 40
5.1.3 Control Flow Obfuscation 45
5.1.4 A complete flow of the propose approach 46
5.1.5 Tamper Proofing Dominant Path Algorithms 47
5.2 Implementation 47
5.3 Security Analysis 49
5.4 Summary 51
CHAPTER 6 TOWARD ROBUSTLY PROTECT SOFTWARE WATERMARKING BY OBFUSCATION AND TAMPER-PROOFING 52
6.1 Introduction 52
6.2 Implementation 52
6.2.1 Destroy Pattern Obfuscation 52
6.2.2 Using Obfuscation Embedded Dynamic Software Watermark 55
6.2.3 Dynamic Software Watermarking 56
6.2.4 Store in the data of byte 58
6.2.5 Tamper-proofing Algorithm 58
6.3 Self de-watermarking 59
6.4 Experiment Results 60
6.5 Toward Robustly Protecting the Software Watermark of a Dominant Path 60
6.6 Discussions 63
6.6.1 Resist Subtractive Attack 63
6.6.2 Resist Additive Attack 63
6.6.3 Resist Distortive Attack 64
6.6.4 Resist Collusive Attack 64
6.7 Summary 64
CHAPTER 7 CONCLUSION AND FUTURE WORKS 65
REFERENCES 67
APPENDIX A TAMPER PROOFING DOMINANT PATH ALGORITHM 73
APPENDIX B PROTOTYPE 76
B.1 Web site 76
B.2 Setup and Operation 76
B.2.1 Three Control Flow Obfuscation Methods 76
B.2.2 Tamper-proofing Basis Path Using Oblivious Hashing 77
B.2.3 Toward Robustly Protecting Data of a Dominant Path in a Java Method 79
B.2.4 Software Watermarking by Obfuscation and Tamper-proofing Techniques 80
自述 …………………………………………………………………………………….83

[1]E. J. Chikofsky and J. H. Cross, “Reverse Engineering and Design Recovery: A Taxonomy”, IEEE Software, 1990, vol.7, no.1, pp.13-17.
[2]Hans Peter van Vliet, “Mocha - The Java Decompiler”, v1.0b, 1996, http://www.brouhaha.com/~eric/software/mocha/.
[3]WingSoft Company, “JavaDis - The Java Decompiler”, 1997, http://www.wingsoft.com/wingdis.html.
[4]Jon Meyer and Troy Downing, “Java Virtual Machine”, O'Reilly, 1997, ISBN: 1565921941.
[5]Business Software Alliance, “A Fifth of PC Software in United States is Pirated, Posing Challenges to High Tech Sector and Cyber Security”, Washington, DC, May 12, 2009, http://www.bsa.org/country/News%20
and%20Events/News%20Archives/global/05122009-idc-globalstudy.aspx.
[6]Christian Collberg and Clark Thomborson, “Watermarking, Tamper-Proofing, and Obfuscation - Tools for Software Protection”, IEEE Transactions on Software Engineering, 2002, vol.28, no.8, pp.735-746.
[7]Gleb Naumovich and Nasir Memon, “Preventing Piracy, Reverse Engineering, and Tampering”, IEEE Computer Society Press, 2003, vol.36, no.7, pp.64-71.
[8]Jien-Tsai Chan and Wuu Yang, “Advanced Obfuscation Techniques for Java Bytecode”, The Journal of Systems and Software, 2004, vol.71, no.1-2, pp.1-10.
[9]Retrologic Systems, “RetroGuard for Java Bytecode Obfuscation”, Retrologic Systems, 2006, http://www.retrologic.com/retroguard-
main.html.
[10]Shafi Goldwasser, “Program Obfuscation and One-Time Programs Program Obfuscation and One-Time Programs”, Lecture Notes in Computer Science, 2008, Vol. 4964, pp. 333-334.
[11]Xuesong Zhang, Fengling He, Wanli Zuo, “An Inter-Classes Obfuscation Method for Java Program”, Information Security and Assurance (ISA 2008), 2008, pp.360-365.
[12]D. Curran, N.J. Hurley and M. O. Cinneide, “Securing Java through Software Watermarking”, Proceedings of the 2nd international conference on Principles and practice of programming in Java, 2003, pp.145 - 148.
[13]Geneviève Arboit, “A Method for Watermarking Java Programs via Opaque Predicates”, Fifth International Conference on Electronic Commerce Research (ICECR-5), 2002, pp.1-8.
[14]Xuesong Zhang, Fengling He and Wanli Zuo, “Hash Function Based Software Watermarking”, Advanced Software Engineering and Its Applications (ASEA 2008), 2008, pp.95-98.
[15]Ibrahim Kamel and Qutaiba Albluwi, “A Robust Software Watermarking for Copyright Protection”, Elsevier Computers and Security International Journal, 2009, In Press.
[16]Xuesong Zhang, Fengling He and Wanli Zuo, “A Java Program Tamper-Proofing Method”, International Conference on Security Technology (SECTECH '08), 2008, pp. 71-74.
[17]Clark Thomborson Jasvir, Clark Thomborson, Jasvir Nagra, Ram Somaraju and Charles He, “Tamper-proofing Software Watermarks”, Proceedings of the second workshop on Australasian information security, Data Mining and Web Intelligence, and Software Internationalisation, 2004, pp. 27-36.
[18]David F. Bacon, Susan L. Graham and Oliver J. Sharp. “Compiler Transformations for High-performance Computing”, ACM Computing Surveys, 1994, vol.26, no.4, pp 345-420, http://www.acm.org/pubs/toc/
Abstracts/0360-0300/197406.html.
[19]Ting-Wei Hou, Hsiang-Yang Chen and Ming-Hsiu Tsai, “Three Control Flow Obfuscation Methods for Java Software”, IEE Proceedings Software, 2006, vol.153, no.2, pp.80-86.
[20]Hsiang-Yang Chen, Ting-Wei Hou and Chun-Liang Lin, “Tamper-proofing Basis Path by Using Oblivious Hashing on Java”, ACM SIGPLAN Notices, 2007, vol.42, no.2, pp.9-16.
[21]Ting-Wei Hou and Hsiang-Yang Chen, ”Toward Robustly Protecting Data of a Dominant Path in a Java Method”, Journal of the Chinese Institute of Engineers, (98/04/13 Accepting).
[22]Douglas Low, Java Control Flow Obfuscation, Master’s Thesis, Department of Computer Science, University of Auckland, New Zealand, 1998.
[23]Hanpeter van Vliet, “Crema: the Java Obfuscator”, 1996, http://www.brouhaha.com/~eric/computers/mocha.html.
[24]Christian Collberg, Clark Thomborson and Douglas Low, “Manufacturing Cheap, Resilient, and Stealthy Opaque Constructs”, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1998, pp.184-196.
[25]Chenxi Wang, A Security Architecture for Survivable Systems, PhD Dissertation, Department of Computer Science, University of Virginia, 2001, ftp://ftp.cs.virginia.edu/pub/dissertations/2001-01_abs.html
[26]Stanley Chow, Yuan Gu, Harold Johnson and Vladimir A. Zakharov, “An Approach to the Obfuscation of Control-Flow of Sequential Computer Programs”, Information Security, 4th International Conference, Lecture Notes in Computer Science, 2001, vol.2200, pp.144-155.
[27]Ting-Wei Hou, Hsiang-Yang Chen and Ming-Hsiu Tsai, “Crossover Obfuscator”, 2005, http://192.192.111.113/research/crossover/.
[28]W. W. Peterson, T. Kasami and N. Tokura, “On the Capabilities of While, Repeat, and Exit Instructions”, Communications of the ACM, 1973, vol.16, no.8, pp.503-512.
[29]Markus Jakobsson and Michael K. Reiter, “Discouraging Software Piracy Using Software Aging”, Proceedings of the first ACM Workshop on Security and Privacy in Digital Rights Management, Lecture Notes in Computer Science, 2002, vol.2320, pp.1-12.
[30]Stanley Chow, Phil Eisen, Harold Johnson and Paul C Van Oorschot, “A White-box DES Implementation for DRM Applications”, Proceedings of 2nd ACM Workshop on Digital Rights Management, Lecture Notes in Computer Science, 2003, vol.2696, pp.1-15.
[31]Chun-Wei Liao and Wei-Bin Lee, “Key Management for Encrypted Storage on a GRID”, Journal of the Chinese Institute of Engineers, 2008, vol.31, no.7, pp.1141-1149.
[32]David Lie, Chandramohan Thekkath, Mark Mitchell, Patrick Lincoln, Dan Boneh, John Mitchell and Mark Horowitz, “Architectural Support for Copy and Tamper Resistant Software”, Proceedings of 9th International Conference on Architectural Support for Programming Languages and Operating Systems, 2000, pp.168-177.
[33]Yuqun Chen, Ramwarathnam Venkatesan, Matthew Cary, Ruoming Pang, Saurabh Sinha, Jakubowski Mariusz H., “Oblivious Hashing: a Stealthy Software Integrity Verification Primitive”, Information Hiding, 5th International Workshop, Lecture Notes in Computer Science, 2003, vol.2578, pp.400-414.
[34]Hoi Chang and Mikhail J. Atallah, “Protecting Software Codes by Guards”, Proceedings of the ACM Workshop on Security and Privacy in Digital Rights Management, Lecture Notes in Computer Science, 2001, vol.2320, pp.160-175.
[35]Christian Collberg and Clark Thomborson, “Software Watermarking: Models and Dynamic Embeddings”, Principles of Programming Languages, 1999, pp.311-324.
[36]Robert L. Davidson and Nathan Myhrvold, “Method and System for Generating and Auditing a Signature for a Computer Program”, US Patent 5,559,884, 1996, Assignee: Microsoft Corporation.
[37]Gang. Qu and Miodrag Potkonjak, “Analysis of Watermarking Techniques for Graph Coloring Problem”, IEEE/ACM International Conference on Computer Aided Design, 1998, pp.190-193.
[38]Ramarathnam Venkatesan, Vijay Vazirani and Saurabh Sinha, “A Graph Theoretic Approach to Software Watermarking”, 4th International Information Hiding Workshop, 2001, pp.1-8.
[39]Patrick Cousot and Radhia Cousot, “An Abstract Interpretation-based Framework for Software Watermarking”, Principles of Programming Languages, 2003, pp.311-324.
[40]Arboit, Genevieve, “A Method for Watermarking Java Programs via Opaque Predicates”, Fifth International Conference on Electronic Commerce Research, 2002, pp.1-8.
[41]Yong He, Tamperproofing a Software Watermark by Encoding Constants, Master’s thesis, University of Auckland, 2002.
[42]Jerome Miecznikowski and Laurie Hendren, “Decompiling Java Using Staged Encapsulation”, Proceeding of the 8th Conference on Reverse Engineering, 2001, pp.368-374.
[43]Todd A Proebsting and Scott A Watterson, “Krakatoa: Decompliation in Java (Does Bytecode Reveal Source?)”, Proceedings of the Third USENIX Conference on Object-Oriented Technologies and Systems, 1997, pp.185-197.
[44]Patrick Lam, “Of Graphs and Coffi Grounds: Decompiling Java”, Sable Technical Report no.6, McGill University School of Computer Science, Sable Research Group, 1998.
[45]Sureshot Software Co., Ltd., “Cavaj - The Java Decompiler”, v1.11, 2002, http://www.bysoft.se/sureshot/cavaj/.
[46] Michael A. Gonsalves, “ClassSpy - The Java Decompiler”, v2.0, 2002, http://www.brothersoft.com/Software_Developer_Miscellaneous_ClassSpy_6712.html.
[47]McGill, “Dava - The Java Decompiler”, v1.0.0, 2001, http://www.program-transformation.org/Transform/DecompilationDava#About_Dava.
[48]Decafe, “Decafe - The Java Decompiler”, v3.6, 1999, http://descargas.terra.es/informacion_extendida.phtml?n_id=8685&plat=1.
[49]Atanas Neshkov, “Welcome to DJ Java Decompiler”, v3.9.9.91, 2002, http://members.fortunecity.com/neshkov/dj.html.
[50]Martin Cowley, “FrontEnd Plus - The Java Decompiler” , v1.00, 2001, http://www.softpile.com/Development/Java/Review_03171_index.html.
[51]Pavel Kouznetsov, “Jad - The Java Decompiler”, v1.5.8e2, 2001, http://www.kpdus.com/jad.html.
[52]D&C Software Solutions, “jAscii - The Java Decompiler”, v1.0.20, 2003, http://www.program-transformation.org/Transform/DecompilationJasciiTest.
[53]Sureshot Software Co., Ltd., “JCavaj - The Java Decompiler”, v1.00, 2002, http://www.sureshotsoftware.com/jcavaj/manual.html#chapter1.
[54]Jochen Hoenicke. Canonic, “JODE - The Java Decompiler”, v1.1.1, May. 2001, http://jode.sourceforge.net/.
[55]GNU GPL, “JReversePro - The Java Decompiler”, v1.4.1, 2002, http://jrevpro.sourceforge.net/.
[56]Eastridge Technology, “Jshrink - The Java Decompiler” , v2.36, 1997, http://www.e-t.com/jshrink.html.
[57]MoleSoftware, “mDeJava - The Java Decompiler” , v1.0b, 2000, http://molesoftware.hypermart.net/.
[58]Basile Lemaire, “NMI’s Java Class Viewer - The Java Decompiler”, v4.7, 1999, http://www.jreveal.org/cgi-bin/resource.pl?resid=4397.
[59]SourceTec Software Co., Ltd., “SourceTec - The Java Decompiler”, v1.1, 1997, http://www.sothink.com/product/javadecompiler/index.htm.
[60]Chung Laung Liu, “Elements of Discrete Mathematic”, McGraw-Hill, 1998, pp.346-349, ISBN:007038133X.
[61]A. B. Konovalov, “On the Nilpotency Class of a Multiplicative Group of a Modular Group Algebra of a Dihedral 2-group”, Ukrainian Mathematical Journal, 1995, vol.47, no.1, pp.42-49.
[62]Rainer Güting, “Subtractive Abelian Groups”, Notre Dame Journal of Formal Logic, 1975, vol.XVI, no.3, pp.425-428.
[63]Jon Meyer, “Jasmin” , 1997, http://cat.nyu.edu/~meyer/jvm/.
[64]Thomas J. McCabe, “A Complexity Measure”, IEEE Transactions on Software Engineering, 1976, vol.2, no.4, pp.308-320.
[65]Joseph Poole, “A Method to Determine a Basis Set of Paths to Perform Program Testing”, U.S. Department of Commerce/National Institute of Standards and Technology, NISTIR 5737, 1995.
[66]Raja Vallée-Rai, Laurie Hendren, Vijay Sundaresan, Patrick Lam, Etienne Gagnon and Phong Co, “Soot - a Java Bytecode Optimization Framework”, Proceedings of CASCON, 1999, pp.125-135, http://www.sable.mcgill.ca/soot/.
[67]Pentagon Software Corporation, “Java CaffeineMark 3.0”, Pentagon Software Corporation, Illinois, USA, 1999.
[68]D. Harel, , “A Linear Algorithm for Finding Dominators in Flow Graphs and Related Problems”, Proceedings of 17th Annual ACM Symposium on Theory of Computing, 1985, pp.185-194.
[69]Wang, Jonathan Hill, John Knight and Jack Davidson, “Software Tamper Resistance Obstructing Static Analysis of Programs”, Technical Report CS-2000-12, Department of Computer Science, University of Virginia, Virginia, USA, 2000.
[70]Stanley Chow, Yuan Gu, Harold Johnson and Vladimir A. Zakharov, “An Approach to the Obfuscation of Control-flow of Sequential Computer Programs”, Proceedings of the 4th International Information Security Conference, Lecture Notes in Computer Science, 2001, vol.2200, pp.144-155.
[71]Akito Monden, Antoine Monsifrot and Clark Thomborson, “A Framework for Obfuscated Interpretation”, Proceedings of the Second Australasian Information Security Workshop, 2004, pp.7-16.
[72] Akito Monden, Hajimu Iida and Ken-ichi Matsumoto, “A Practical Method for Watermarking Java Programs”, 24th Computer Software and Applications Conference, 2000. Also published in SCIS’98 (Japanese).
[73]C. Collberg, E. Carter, S. Debray, A. Huntwork, C. Linn and M. Stepp, “Dynamic Path Based Software Watermarking”, Proceedings of the Conference on Programming Language Design and Implementation, 2004, pp.107-118.
[74]Christian Collberg and Clark Thomborson, “Software Watermarking: Models and Dynamic Embeddings”, Conference Record of POPL '99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1999, pp.311-324.