Fast Approximate Matching of Programs for Protecting Libre/Open Source Software by Using Spatial Indexes

@inproceedings{citeulike:2902400, abstract = {To encourage open source/libre software development, it is desirable to have tools that can help to identify open source license violations. This paper describes the implementation of a tool that matches open source programs embedded inside pirate programs. The problem of binary program matching can be approximated by analyzing the similarity of program fragments generated from low-level instructions. These fragments are syntax trees that can be compared by using a tree distance function. Tree distance functions are generally very costly. Sequentially calculating the similarities of fragments with them becomes prohibitively expensive. In this paper we experimentally demonstrate how a spatial index can be used to substantially increase matching performance. These techniques allowed us to do exhaustive experiments that confirmed previous results on the subject. The paper also introduces the novel idea of using information retrieval techniques for calculating the similarity of bags of program fragments. It is possible to identify programs even when they are heavily obfuscated with the innovative approach described here.}, author = {Muller, A. J. and Shinohara, T. }, booktitle = {Source Code Analysis and Manipulation, 2007. SCAM 2007. Seventh IEEE International Working Conference on}, citeulike-article-id = {2902400}, doi = {10.1109/SCAM.2007.15}, journal = {Source Code Analysis and Manipulation, 2007. SCAM 2007. Seventh IEEE International Working Conference on}, keywords = {opensource, protection, software}, pages = {111--122}, posted-at = {2008-06-17 13:45:10}, priority = {2}, title = {Fast Approximate Matching of Programs for Protecting Libre/Open Source Software by Using Spatial Indexes}, url = {http://dx.doi.org/10.1109/SCAM.2007.15}, year = {2007} }

TY - CONF ID - citeulike:2902400 L3 - citeulike-article-id:2902400 TI - Fast Approximate Matching of Programs for Protecting Libre/Open Source Software by Using Spatial Indexes T2 - Source Code Analysis and Manipulation, 2007. SCAM 2007. Seventh IEEE International Working Conference on JF - Source Code Analysis and Manipulation, 2007. SCAM 2007. Seventh IEEE International Working Conference on SP - 111 EP - 122 N2 - To encourage open source/libre software development, it is desirable to have tools that can help to identify open source license violations. This paper describes the implementation of a tool that matches open source programs embedded inside pirate programs. The problem of binary program matching can be approximated by analyzing the similarity of program fragments generated from low-level instructions. These fragments are syntax trees that can be compared by using a tree distance function. Tree distance functions are generally very costly. Sequentially calculating the similarities of fragments with them becomes prohibitively expensive. In this paper we experimentally demonstrate how a spatial index can be used to substantially increase matching performance. These techniques allowed us to do exhaustive experiments that confirmed previous results on the subject. The paper also introduces the novel idea of using information retrieval techniques for calculating the similarity of bags of program fragments. It is possible to identify programs even when they are heavily obfuscated with the innovative approach described here. KW - opensource KW - protection KW - software AU - Muller, AJ AU - Shinohara, T PY - 2007/// UR - http://dx.doi.org/10.1109/SCAM.2007.15 ER -