Visible to the public Code Relatives: Detecting Similarly Behaving Software

TitleCode Relatives: Detecting Similarly Behaving Software
Publication TypeConference Paper
Year of Publication2016
AuthorsSu, Fang-Hsiang, Bell, Jonathan, Harvey, Kenneth, Sethumadhavan, Simha, Kaiser, Gail, Jebara, Tony
Conference NameProceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering
PublisherACM
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4218-6
Keywordscode clones, Code relatives, composability, Human Behavior, link analysis, pubcrawl, Resiliency, runtime behavior, static code analysis, subgraph matching
Abstract

Detecting "similar code" is useful for many software engineering tasks. Current tools can help detect code with statically similar syntactic and-or semantic features (code clones) and with dynamically similar functional input/output (simions). Unfortunately, some code fragments that behave similarly at the finer granularity of their execution traces may be ignored. In this paper, we propose the term "code relatives" to refer to code with similar execution behavior. We define code relatives and then present DyCLINK, our approach to detecting code relatives within and across codebases. DyCLINK records instruction-level traces from sample executions, organizes the traces into instruction-level dynamic dependence graphs, and employs our specialized subgraph matching algorithm to efficiently compare the executions of candidate code relatives. In our experiments, DyCLINK analyzed 422+ million prospective subgraph matches in only 43 minutes. We compared DyCLINK to one static code clone detector from the community and to our implementation of a dynamic simion detector. The results show that DyCLINK effectively detects code relatives with a reasonable analysis time.

URLhttp://doi.acm.org/10.1145/2950290.2950321
DOI10.1145/2950290.2950321
Citation Keysu_code_2016