Amain is a scalable tree-based semantic code clone detector by building Markov chains models. We regard the nodes of an AST as different states and build a Markov chains model to transform the complex tree into simple state transitions. After collecting the distance vectors of all states between ASTs, we train a classifier that can assign suitable weights for different states to achieve succinct and effective semantic code clone detection.
Amain is mainly comprised of four phases: AST Generation, State Matrix Construction, Feature Extraction, and Classification.
- AST Generation: The purpose of this phase is to apply static analysis to generate the corresponding AST. The input of this phase is a method and the output is an AST.
- State Matrix Construction: The purpose of this phase is to transform the AST into a Markov chain-based state matrix. The input of this phase is an AST and the output is a state transfer matrix.
- Feature Extraction: The purpose of this phase is to calculate the distance vectors (\ie features) of two state transfer matrices. The input of this phase is two state transfer matrices and the output is a feature vector.
- Classification: The purpose of this phase is to determine whether two methods are semantically similar or not. The input of this phase is a feature vector and the output is to report the detection results.
The source code and dataset of Amain are published here.
Amain
|-- get_matrix.py // implement the first two phases: AST Generation and State Matrix Construction
|-- get_distance.py // implement the Feature Extraction phase
|-- classification.py // implement the Classification phase - Input: dataset with source codes
- Output: state transfer matrices of source codes
python get_matrix.py
- Input: state transfer matrices and code pairs
- Output: feature vectors of code pairs
python get_distance.py
- Input: feature vectors of dataset
- Output: recall, precision, and F1 scores of machine learning algorithms
python classification.py
| Tool | Parameters |
|---|---|
| SourcererCC | Min lines: 6, Similarity threshold: 0.7 |
| Deckard | Min tokens: 100, Stride: 2, Similarity threshold: 0.9 |
| RtvNN | RtNN phase: hidden layer size: 400, epoch: 25, |
| ASTNN | symbols embedding size: 128, hidden dimension: 100, mini-batch: 64, epoch: 5, threshold: 0.5, learning rate of AdaMax: 0.002 |
| SCDetector | distance measure: Cosine distance, dimension of token vector: 100, threshold: 0.5, learning rate: 0.0001 |
| DeepSim | Layers size: 88-6, (128x6-256-64)-128-32, epoch: 4, Initial learning rate: 0.001, |
| CDLH | Code length 32 for learned binary hash codes, size of word embeddings: 100 |
| TBCNN | Convolutional layer dim size: 300，dropout rate: 0.5, batch size: 10 |
| FCCA | Size of hidden states: 128(Text), 128(AST), embedding size: 300(Text), 300(AST), 64(CFG) clipping gradient range: (-1.2，1.2), epoch: 50, initial learning rate: 0.0005, dropout:0.6, batchsize: 32 |
Yueming Wu, Siyue Feng, Deqing Zou, and Hai Jin. 2022. Detecting Semantic Code Clones by Building AST-based Markov Chains Model. In 37th IEEE/ACM International Conference on Automated Software Engineering (ASE'22), October 10–14, 2022, Rochester, MI, USA. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3551349.3560426
If you use our dataset or source code, please kindly cite our paper:
@INPROCEEDINGS{amain2022,
author={Wu, Yueming and Feng, Siyue and Zou, Deqing and Jin, Hai},
booktitle={2022 IEEE/ACM 37th International Conference on Automated Software Engineering (ASE)},
title={Detecting Semantic Code Clones by Building AST-based Markov Chains Model},
year={2022},
doi={10.1145/3551349.3560426}}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent