Detecting code clones in binary executables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Detecting code clones in binary executables

Full text

Pdf (895 KB)

Source

International Symposium on Software Testing and Analysis archive
Proceedings of the eighteenth international symposium on Software testing and analysis table of contents

Chicago, IL, USA

SESSION: Testing and analysis tools #1 table of contents

Pages 117-128

Year of Publication: 2009

ISBN:978-1-60558-338-9

Authors

Andreas Sæbjørnsen	University of California, Davis, Davis, CA, USA
Jeremiah Willcock	Indiana University, Bloomington, IN, USA
Thomas Panas	Lawrence Livermore National Laboratory, Livermore, CA, USA
Daniel Quinlan	Lawrence Livermore National Laboratory, Livermore, CA, USA
Zhendong Su	University of California, Davis, Davis, CA, USA

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering
SIGPLAN: ACM Special Interest Group on Programming Languages
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 107, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1572272.1572287 What is a DOI?

ABSTRACT

Large software projects contain significant code duplication, mainly due to copying and pasting code. Many techniques have been developed to identify duplicated code to enable applications such as refactoring, detecting bugs, and protecting intellectual property. Because source code is often unavailable, especially for third-party software, finding duplicated code in binaries becomes particularly important. However, existing techniques operate primarily on source code, and no effective tool exists for binaries.

In this paper, we describe the first practical clone detection algorithm for binary executables. Our algorithm extends an existing tree similarity framework based on clustering of characteristic vectors of labeled trees with novel techniques to normalize assembly instructions and to accurately and compactly model their structural information. We have implemented our technique and evaluated it on Windows XP system binaries totaling over 50 million assembly instructions. Results show that it is both scalable and precise: it analyzed Windows XP system binaries in a few hours and produced few false positives. We believe our technique is a practical, enabling technology for many applications dealing with binary code.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	IDA Pro disassembler. http://www.datarescue.com.
	2	JPlag. http://www.jplag.de.
	3	A. Andoni and P. Indyk. E2LSH: Exact Euclidean locality-sensitive hashing. Web: http://www.mit.edu/~andoni/LSH/, 2004.
	4	Alexandr Andoni , Piotr Indyk, Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Communications of the ACM, v.51 n.1, January 2008 [doi>10.1145/1327452.1327494]
	5	Brenda S. Baker, Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal on Computing, v.26 n.5, p.1343-1362, Oct. 1997 [doi>10.1137/S0097539793246707]
	6	Hamid Abdul Basit , Stan Jarzabek, Detecting higher-level similarity patterns in programs, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
	7	Ira D. Baxter , Christopher Pidgeon , Michael Mehlich, DMS®: Program Transformations for Practical Scalable Software Evolution, Proceedings of the 26th International Conference on Software Engineering, p.625-634, May 23-28, 2004
	8	D. Bruschi, L. Martignoni, and M. Monga. Detecting self-mutating malware using control flow graph matching. In DIMVA, pages 129--143, 2006.
	9	Mihai Christodorescu , Somesh Jha, Static analysis of executables to detect malicious patterns, Proceedings of the 12th conference on USENIX Security Symposium, p.12-12, August 04-08, 2003, Washington, DC
	10	Mihai Christodorescu , Somesh Jha, Testing malware detectors, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
	11	Mihai Christodorescu , Somesh Jha , Sanjit A. Seshia , Dawn Song , Randal E. Bryant, Semantics-Aware Malware Detection, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.32-46, May 08-11, 2005 [doi>10.1109/SP.2005.20]
	12	Mark Gabel , Lingxiao Jiang , Zhendong Su, Scalable detection of semantic clones, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368132]
	13	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	14	A. Hemel. The GPL compliance engineering guide. http://www.loohuis-consulting.nl/downloads/compliance-manual.pdf.
	15	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
	16	Lingxiao Jiang , Ghassan Misherghi , Zhendong Su , Stephane Glondu, DECKARD: Scalable and Accurate Tree-Based Detection of Code Clones, Proceedings of the 29th international conference on Software Engineering, p.96-105, May 20-26, 2007 [doi>10.1109/ICSE.2007.30]
	17	Toshihiro Kamiya , Shinji Kusumoto , Katsuro Inoue, CCFinder: a multilinguistic token-based code clone detection system for large scale source code, IEEE Transactions on Software Engineering, v.28 n.7, p.654-670, July 2002 [doi>10.1109/TSE.2002.1019480]
	18	Raghavan Komondoor , Susan Horwitz, Using Slicing to Identify Duplication in Source Code, Proceedings of the 8th International Symposium on Static Analysis, p.40-56, July 16-18, 2001
	19	C. Kruegel, D. Mutz, W. Robertson, and G. Vigna. Polymorphic worm detection using structural information of executables. In Recent Adv. in Intrusion Detection, pages 207--226. Springer-Verlag, 2005.
	20	Zhenmin Li , Shan Lu , Suvda Myagmar , Yuanyuan Zhou, CP-Miner: a tool for finding copy-paste and related bugs in operating system code, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.20-20, December 06-08, 2004, San Francisco, CA
	21	Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
	22	M. Schordan and D. Quinlan. A source-to-source architecture for user-defined optimizations. In Joint Modular Languages Conference, volume 2789 of Lecture Notes in Computer Science, pages 214--223. Springer Verlag, Aug. 2003.
	23	David Schuler , Valentin Dallmeier , Christian Lindig, A dynamic birthmark for java, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321672]
	24	A. Schulman. Finding binary clones with opstrings and function digests. Doctor Dobb's J, 30(9):64--70, 2005.
	25	Gregory Shakhnarovich , Trevor Darrell , Piotr Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing), The MIT Press, 2006
	26	Vera Wahler , Dietmar Seipel , Jurgen Wolff v. Gudenberg , Gregor Fischer, Clone Detection in Source Code by Frequent Itemset Techniques, Proceedings of the Source Code Analysis and Manipulation, Fourth IEEE International Workshop, p.128-135, September 15-16, 2004 [doi>10.1109/SCAM.2004.5]
	27	Heng Yin , Dawn Song , Manuel Egele , Christopher Kruegel , Engin Kirda, Panorama: capturing system-wide information flow for malware detection and analysis, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315261]