814 计 算 机 学 报 2007年 mation frameworks by abstract interpretation//Proceedings 参考文献 of the ACM SIGPLAN Conference on Principles of Program- ming Languages.Portland Oregon.2002:178-190 [9]Cousot P.Cousot R.Abstract interpretation:A unified lat- [1]Collberg C.Clark T.Douglas L.A taxonomy of obfuscating tice model for static analysis of program by construction or transformations.Department of Computer Science,the Uni- approximation of fixpoints//Proceedings of the ACM SIGP. versity of Auckland:Technical Report #148,1997 LAN on Principles of Programming Languages.Los Angel- [2]Wang C X.A security architecture for survivability mecha- es.California.1977:238-252 nisms[Ph.D.dissertation].University of Virginia.Depart- [10] Gregory Wroblewski.General method of program code ob- ment of Computer Science,2000 fuscation[Ph.D.dissertation].Wroclaw University of Tech- [3]Ogiso T.Sakabe Y.Software obfuscation on a theoretical nology.Institute of Engineering Cybernetics.2002 basis and its implementation.IEEE Transactions on Funda- [11]Chen Yi-Yun,Zhang Yu.Theory of Compiler.Beijing: mentals,2003,E86-A(1):176-186 Higher Education Press,2003(in Chinese) [4]Douglas L.Protecting java code via code obfuscation.ACM (陈意云，张昱.编译原理.北京：高等教有出版社，2003) Crossroads,1998,4(3):21-23 [12]Li Yong-Xiang,Chen Yi-Yun.Technique of code obfuscation [5]Barak B.Goldreich O.Impagliazzo R.Rudich S.Sahai A. based on function pointer array.Chinese Journal of Comput- Vadhan S P.Yang K.On the (im)possibility of obfuscating ers,2004,27(12):1706-1711(in Chinese) programs//Kilian J ed.Proceedings of the 21st Annual Inter- (李永祥，陈意云.基于函数指针数组的代码迷惑技术.计算 national Cryptology Conference on Advances in Cryptology. 机学报，2004,27(12)：1706-1711) Santa Barbara.California:Springer-Verlag.2001.19-23: [13] Cousot P.Constructive design of a hierarchy of semantics of 1-18 a transition system by abstract interpretation.Theoretical [6]Lynn Benjamin.Manoj P.Amit S.Positive results and tech- Computer Science,2002,277(1-2):47-103 niques for obfuscation//Proceedings of the EuroCRYPT.In- [14]Dalla Preda M,Giacobazzi R.Semantic-based code obfusca- terlaken.Switzerland.2004:20-39 tion by abstract interpretation//Proceedings of the ICALP'05. [7]Lee B.Larry D.Self-protecting mobile agents obfuscation Lisbon,Portugal,2005:1325-1336 technique evaluation report.Network Associates Laborato- [15]Dalla Preda M.Giacobazzi R.Control code obfuscation by ries:Report #01-036.2002 abstract interpretation//Proceedings of the SEFM'05.Kobl- [8]Cousot P.Cousot R.Systematic design of program transfor- benz,Germany,2005:301-310 GAO Ying,born in 1980.Ph.D. CHEN Yi-Yun,born in 1946.professor,Ph.D.super- candidate.His research interests include visor.His research interests include theory and implementa- theory and implementation of program- tion of programming language,formal description technolo- ming language and the security of mobile gies,and software security. host. Background This research is supported by the National Natural Sci-many researches have shown the limitation of code obfusca- ence Foundation of China(grant No.60473068).Code Obfus- tion as a security method.which puts the application of code cation is a program transformation for the purpose of increas- obfuscation into doubt.Therefore,how to measure and ing the difficulty of program understanding.It is a useful prove the efficiency of code obfuscation is an important prob- method to guarantee the security in mobile agent and protect lem.The contribution of this paper is to present a new for- the program from reverse engineering.At present,the inter- mal framework for proving the efficiency of code obfuscation ests on code obfuscation focus on two major aspects:The algorithm.Based on abstract interpretation framework,the construction of code obfuscation algorithm and the proof of authors construct the comparable code obfuscation frame- its efficiency.Although the construction of code obfuscation work,which can formally prove its efficiency under the limit- algorithm grows more mature.the proof of its efficiency is ed environment of static analysis and compare the efficiency still blank in the formal semantic foundation.Meanwhile, among code obfuscation algorithms.参 考 文 献 ［１］ ＣｏｌｌｂｅｒｇＣ，ＣｌａｒｋＴ，ＤｏｕｇｌａｓＬ．Ａｔａｘｏｎｏｍｙｏｆｏｂｆｕｓｃａｔｉｎｇ ｔｒａｎｓｆｏｒｍａｔｉｏｎｓ．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ｔｈｅＵｎｉ ｖｅｒｓｉｔｙｏｆＡｕｃｋｌａｎｄ：ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ＃１４８，１９９７ ［２］ ＷａｎｇＣＸ．Ａｓｅｃｕｒｉｔｙａｒｃｈｉｔｅｃｔｕｒｅｆｏｒｓｕｒｖｉｖａｂｉｌｉｔｙｍｅｃｈａ ｎｉｓｍｓ［Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ］．ＵｎｉｖｅｒｓｉｔｙｏｆＶｉｒｇｉｎｉａ，Ｄｅｐａｒｔ ｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，２０００ ［３］ ＯｇｉｓｏＴ，ＳａｋａｂｅＹ．Ｓｏｆｔｗａｒｅｏｂｆｕｓｃａｔｉｏｎｏｎａｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓａｎｄｉｔｓｉｍｐｌｅｍｅｎｔａｔｉｏｎ．ＩＥＥＥ ＴｒａｎｓａｃｔｉｏｎｓｏｎＦｕｎｄａ ｍｅｎｔａｌｓ，２００３，Ｅ８６Ａ（１）：１７６１８６ ［４］ ＤｏｕｇｌａｓＬ．Ｐｒｏｔｅｃｔｉｎｇｊａｖａｃｏｄｅｖｉａｃｏｄｅｏｂｆｕｓｃａｔｉｏｎ．ＡＣＭ Ｃｒｏｓｓｒｏａｄｓ，１９９８，４（３）：２１２３ ［５］ ＢａｒａｋＢ，ＧｏｌｄｒｅｉｃｈＯ，ＩｍｐａｇｌｉａｚｚｏＲ，ＲｕｄｉｃｈＳ，ＳａｈａｉＡ， ＶａｄｈａｎＳＰ，ＹａｎｇＫ．Ｏｎｔｈｅ（ｉｍ）ｐｏｓｓｉｂｉｌｉｔｙｏｆｏｂｆｕｓｃａｔｉｎｇ ｐｒｏｇｒａｍｓ／／ＫｉｌｉａｎＪｅｄ．Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２１ｓｔＡｎｎｕａｌＩｎｔｅｒ ｎａｔｉｏｎａｌＣｒｙｐｔｏｌｏｇｙ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ａｄｖａｎｃｅｓｉｎ Ｃｒｙｐｔｏｌｏｇｙ． ＳａｎｔａＢａｒｂａｒａ，Ｃａｌｉｆｏｒｎｉａ：ＳｐｒｉｎｇｅｒＶｅｒｌａｇ，２００１，１９２３： １１８ ［６］ ＬｙｎｎＢｅｎｊａｍｉｎ，ＭａｎｏｊＰ，ＡｍｉｔＳ．Ｐｏｓｉｔｉｖｅｒｅｓｕｌｔｓａｎｄｔｅｃｈ ｎｉｑｕｅｓｆｏｒｏｂｆｕｓｃａｔｉｏｎ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＥｕｒｏＣＲＹＰＴ．Ｉｎ ｔｅｒｌａｋｅｎ，Ｓｗｉｔｚｅｒｌａｎｄ，２００４：２０３９ ［７］ ＬｅｅＢ，ＬａｒｒｙＤ．Ｓｅｌｆｐｒｏｔｅｃｔｉｎｇ ｍｏｂｉｌｅａｇｅｎｔｓｏｂｆｕｓｃａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｅｖａｌｕａｔｉｏｎｒｅｐｏｒｔ．Ｎｅｔｗｏｒｋ ＡｓｓｏｃｉａｔｅｓＬａｂｏｒａｔｏ ｒｉｅｓ：Ｒｅｐｏｒｔ＃０１０３６，２００２ ［８］ ＣｏｕｓｏｔＰ，ＣｏｕｓｏｔＲ．Ｓｙｓｔｅｍａｔｉｃｄｅｓｉｇｎｏｆｐｒｏｇｒａｍｔｒａｎｓｆｏｒ ｍａｔｉｏｎｆｒａｍｅｗｏｒｋｓｂｙａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎ／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆｔｈｅＡＣＭＳＩＧＰＬＡＮＣｏｎｆｅｒｅｎｃｅｏｎＰｒｉｎｃｉｐｌｅｓｏｆＰｒｏｇｒａｍ ｍｉｎｇＬａｎｇｕａｇｅｓ．ＰｏｒｔｌａｎｄＯｒｅｇｏｎ，２００２：１７８１９０ ［９］ ＣｏｕｓｏｔＰ，ＣｏｕｓｏｔＲ．Ａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎ：Ａｕｎｉｆｉｅｄｌａｔ ｔｉｃｅｍｏｄｅｌｆｏｒｓｔａｔｉｃａｎａｌｙｓｉｓｏｆｐｒｏｇｒａｍ ｂｙｃｏｎｓｔｒｕｃｔｉｏｎｏｒ ａｐｐｒｏｘｉｍａｔｉｏｎｏｆｆｉｘｐｏｉｎｔｓ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＡＣＭ ＳＩＧＰ ＬＡＮｏｎＰｒｉｎｃｉｐｌｅｓｏｆＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅｓ．ＬｏｓＡｎｇｅｌ ｅｓ，Ｃａｌｉｆｏｒｎｉａ，１９７７：２３８２５２ ［１０］ Ｇｒｅｇｏｒｙ Ｗｒｏｂｌｅｗｓｋｉ．Ｇｅｎｅｒａｌｍｅｔｈｏｄｏｆｐｒｏｇｒａｍｃｏｄｅｏｂ ｆｕｓｃａｔｉｏｎ［Ｐｈ．Ｄ．ｄｉｓｓｅｒｔａｔｉｏｎ］．ＷｒｏｃｌａｗＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈ ｎｏｌｏｇｙ，ＩｎｓｔｉｔｕｔｅｏｆＥｎｇｉｎｅｅｒｉｎｇＣｙｂｅｒｎｅｔｉｃｓ，２００２ ［１１］ Ｃｈｅｎ ＹｉＹｕｎ，Ｚｈａｎｇ Ｙｕ．Ｔｈｅｏｒｙ ｏｆ Ｃｏｍｐｉｌｅｒ．Ｂｅｉｊｉｎｇ： ＨｉｇｈｅｒＥｄｕｃａｔｉｏｎＰｒｅｓｓ，２００３（ｉｎＣｈｉｎｅｓｅ） （陈意云，张 昱．编译原理．北京：高等教育出版社，２００３） ［１２］ ＬｉＹｏｎｇＸｉａｎｇ，ＣｈｅｎＹｉＹｕｎ．Ｔｅｃｈｎｉｑｕｅｏｆｃｏｄｅｏｂｆｕｓｃａｔｉｏｎ ｂａｓｅｄｏｎｆｕｎｃｔｉｏｎｐｏｉｎｔｅｒａｒｒａｙ．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＣｏｍｐｕｔ ｅｒｓ，２００４，２７（１２）：１７０６１７１１（ｉｎＣｈｉｎｅｓｅ） （李永祥，陈意云．基于函数指针数组的代码迷惑技术．计算 机学报，２００４，２７（１２）：１７０６１７１１） ［１３］ ＣｏｕｓｏｔＰ．Ｃｏｎｓｔｒｕｃｔｉｖｅｄｅｓｉｇｎｏｆａｈｉｅｒａｒｃｈｙｏｆｓｅｍａｎｔｉｃｓｏｆ ａｔｒａｎｓｉｔｉｏｎｓｙｓｔｅｍ ｂｙａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎ．Ｔｈｅｏｒｅｔｉｃａｌ ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，２００２，２７７（１２）：４７１０３ ［１４］ ＤａｌｌａＰｒｅｄａ Ｍ，ＧｉａｃｏｂａｚｚｉＲ．Ｓｅｍａｎｔｉｃｂａｓｅｄｃｏｄｅｏｂｆｕｓｃａ ｔｉｏｎｂｙａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＩＣＡＬＰ′０５． Ｌｉｓｂｏｎ，Ｐｏｒｔｕｇａｌ，２００５：１３２５１３３６ ［１５］ ＤａｌｌａＰｒｅｄａ Ｍ，ＧｉａｃｏｂａｚｚｉＲ．Ｃｏｎｔｒｏｌｃｏｄｅｏｂｆｕｓｃａｔｉｏｎｂｙ ａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎ／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＳＥＦＭ′０５．Ｋｏｂｌ ｂｅｎｚ，Ｇｅｒｍａｎｙ，２００５：３０１３１０ 犌犃犗犢犻狀犵，ｂｏｒｎｉｎ１９８０，Ｐｈ．Ｄ． ｃａｎｄｉｄａｔｅ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅ ｔｈｅｏｒｙａｎｄｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｐｒｏｇｒａｍ ｍｉｎｇｌａｎｇｕａｇｅａｎｄｔｈｅｓｅｃｕｒｉｔｙｏｆｍｏｂｉｌｅ ｈｏｓｔ． 犆犎犈犖犢犻犢狌狀，ｂｏｒｎｉｎ１９４６，ｐｒｏｆｅｓｓｏｒ，Ｐｈ．Ｄ．ｓｕｐｅｒ ｖｉｓｏｒ．Ｈｉｓｒｅｓｅａｒｃｈｉｎｔｅｒｅｓｔｓｉｎｃｌｕｄｅｔｈｅｏｒｙａｎｄｉｍｐｌｅｍｅｎｔａ ｔｉｏｎｏｆｐｒｏｇｒａｍｍｉｎｇｌａｎｇｕａｇｅ，ｆｏｒｍａｌｄｅｓｃｒｉｐｔｉｏｎｔｅｃｈｎｏｌｏ ｇｉｅｓ，ａｎｄｓｏｆｔｗａｒｅｓｅｃｕｒｉｔｙ． 犅犪犮犽犵狉狅狌狀犱 ＴｈｉｓｒｅｓｅａｒｃｈｉｓｓｕｐｐｏｒｔｅｄｂｙｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉ ｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａ（ｇｒａｎｔＮｏ．６０４７３０６８）．ＣｏｄｅＯｂｆｕｓ ｃａｔｉｏｎｉｓａｐｒｏｇｒａｍｔｒａｎｓｆｏｒｍａｔｉｏｎｆｏｒｔｈｅｐｕｒｐｏｓｅｏｆｉｎｃｒｅａｓ ｉｎｇｔｈｅｄｉｆｆｉｃｕｌｔｙｏｆｐｒｏｇｒａｍ ｕｎｄｅｒｓｔａｎｄｉｎｇ．Ｉｔｉｓａｕｓｅｆｕｌ ｍｅｔｈｏｄｔｏｇｕａｒａｎｔｅｅｔｈｅｓｅｃｕｒｉｔｙｉｎｍｏｂｉｌｅａｇｅｎｔａｎｄｐｒｏｔｅｃｔ ｔｈｅｐｒｏｇｒａｍｆｒｏｍｒｅｖｅｒｓｅｅｎｇｉｎｅｅｒｉｎｇ．Ａｔｐｒｅｓｅｎｔ，ｔｈｅｉｎｔｅｒ ｅｓｔｓｏｎｃｏｄｅｏｂｆｕｓｃａｔｉｏｎｆｏｃｕｓｏｎｔｗｏ ｍａｊｏｒａｓｐｅｃｔｓ：Ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎｏｆｃｏｄｅｏｂｆｕｓｃａｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｔｈｅｐｒｏｏｆｏｆ ｉｔｓｅｆｆｉｃｉｅｎｃｙ．Ａｌｔｈｏｕｇｈｔｈｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆｃｏｄｅｏｂｆｕｓｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍｇｒｏｗｓｍｏｒｅｍａｔｕｒｅ，ｔｈｅｐｒｏｏｆｏｆｉｔｓｅｆｆｉｃｉｅｎｃｙｉｓ ｓｔｉｌｌｂｌａｎｋｉｎｔｈｅｆｏｒｍａｌｓｅｍａｎｔｉｃｆｏｕｎｄａｔｉｏｎ．Ｍｅａｎｗｈｉｌｅ， ｍａｎｙｒｅｓｅａｒｃｈｅｓｈａｖｅｓｈｏｗｎｔｈｅｌｉｍｉｔａｔｉｏｎｏｆｃｏｄｅｏｂｆｕｓｃａ ｔｉｏｎａｓａｓｅｃｕｒｉｔｙｍｅｔｈｏｄ，ｗｈｉｃｈｐｕｔｓｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｃｏｄｅ ｏｂｆｕｓｃａｔｉｏｎｉｎｔｏ ｄｏｕｂｔ．Ｔｈｅｒｅｆｏｒｅ，ｈｏｗ ｔｏ ｍｅａｓｕｒｅ ａｎｄ ｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｃｏｄｅｏｂｆｕｓｃａｔｉｏｎｉｓａｎｉｍｐｏｒｔａｎｔｐｒｏｂ ｌｅｍ．Ｔｈｅｃｏｎｔｒｉｂｕｔｉｏｎｏｆｔｈｉｓｐａｐｅｒｉｓｔｏｐｒｅｓｅｎｔａｎｅｗｆｏｒ ｍａｌｆｒａｍｅｗｏｒｋｆｏｒｐｒｏｖｉｎｇｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｃｏｄｅｏｂｆｕｓｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｂａｓｅｄｏｎａｂｓｔｒａｃｔｉｎｔｅｒｐｒｅｔａｔｉｏｎｆｒａｍｅｗｏｒｋ，ｔｈｅ ａｕｔｈｏｒｓｃｏｎｓｔｒｕｃｔｔｈｅｃｏｍｐａｒａｂｌｅｃｏｄｅｏｂｆｕｓｃａｔｉｏｎｆｒａｍｅ ｗｏｒｋ，ｗｈｉｃｈｃａｎｆｏｒｍａｌｌｙｐｒｏｖｅｉｔｓｅｆｆｉｃｉｅｎｃｙｕｎｄｅｒｔｈｅｌｉｍｉｔ ｅｄｅｎｖｉｒｏｎｍｅｎｔｏｆｓｔａｔｉｃａｎａｌｙｓｉｓａｎｄｃｏｍｐａｒｅｔｈｅｅｆｆｉｃｉｅｎｃｙ ａｍｏｎｇｃｏｄｅｏｂｆｕｓｃａｔｉｏｎａｌｇｏｒｉｔｈｍｓ． ８１４ 计 算 机 学 报 ２００７年