Identifying similar code in software systems can assist many software engineering tasks such as program understanding and software refactoring. While most approaches focus on identifying code that looks alike, some techniques aim at detecting code that functions alike. Detecting these functional clones — code that functions alike — in object oriented languages remains an open question because of the difficulty in exposing and comparing programs' functionality effectively. We propose a novel technique, In-Vivo Clone Detection, that detects functional clones in arbitrary programs by identifying and mining their inputs and outputs. The key insight is to use existing workloads to execute programs and then measure functional similarities between programs based on their inputs and outputs, which mitigates the problems in object oriented languages reported by prior work. We implement such technique in our system, HitoshiIO, which is open source and freely available. Our experimental results show that HitoshiIO detects more than 800 functional clones across a corpus of 118 projects. In a random sample of the detected clones, HitoshiIO achieves 68+% true positive rate with only 15% false positive rate.

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.

Query auto-completion (QAC) is an important feature of a search system that helps users reach their target queries faster. Personalization is a powerful technique that improves the relevance of QAC to the current query. This paper proposes a novel framework, EXOS, to augment the native query by important tokens in the user's search contexts to provide personalized auto-completions dynamically. EXOS is composed of three major steps: expansion, selection and boosting. Each token from the user's search contexts is evaluated and stored by EXOS. The tokens with the highest importance are chosen by the expansion step to augment the native query from the user. These augmented queries are used to retrieve QAC results. The selection and boosting models then extract qualified results, merge and re-rank these results based on their query importance to provide the user with a personalized QAC. We designed two large-scale experiments with over six million queries to evaluate the effectiveness of EXOS. Compared with an advanced MostPopularCompletion system, EXOS has 126% gain on Mean Reciprocal Rank (MRR) and 270% gain on Success Rate at Top-1 in a prefix-based experiment. EXOS shows 10.5% gain on first-token MRR and about 9% gain on Token Saved Rate in a token-based experiment. The results of our experiments show that EXOS significantly enhances the relevance of QAC by predicting the user's target query with using fewer keystrokes.