A software birthmark is a set of characteristics extracted from an executable program. It is difficult to remove by modifying the program binary and is specific enough to distinguish it from other programs. Software birthmark techniques are used to detect program theft by determining the similarity between two different programs. In this paper, we propose a software birthmark based on a graph-based structure comparison scheme. By enhancing the function level comparison and the basic block level comparison algorithms, we show that software birthmarks can have improved resilience compared to those of the original graph-based structure comparison scheme.