A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
Dataset of Functionally Equivalent Java Methods and Its Application to Evaluating Clone Detection Tools
Abra o Access
Conjunto de dados de métodos Java funcionalmente equivalentes e sua aplicação para avaliar ferramentas de detecção de clones

Yoshiki HIGO

  • Exibições de texto completo

    275

  • Cite isto
  • Free PDF (3MB)

Resumo:

As linguagens de programação modernas de alto nível possuem uma ampla variedade de gramática e podem implementar a funcionalidade necessária de diferentes maneiras. Os autores acreditam que existe uma grande quantidade de código que implementa a mesma funcionalidade de maneiras diferentes, mesmo em software de código aberto, onde o código-fonte está disponível publicamente, e que, ao coletar esse código, um conjunto de dados útil pode ser construído para vários estudos em software. Engenharia. Neste estudo, construímos um conjunto de dados de pares de Java métodos que possuem a mesma funcionalidade, mas estruturas diferentes, de aproximadamente 314 milhões de linhas de código-fonte. Para construir este conjunto de dados os autores usaram uma técnica automatizada de geração de testes EvoSuite. Os casos de teste gerados por técnicas automatizadas de geração de teste têm a propriedade de que os casos de teste sempre são bem-sucedidos. Na construção do conjunto de dados, usando esta propriedade, os casos de teste gerados a partir de dois métodos foram executados entre si para determinar automaticamente se o comportamento dos dois métodos é o mesmo até certo ponto. Pares de métodos para os quais todos os casos de teste tiveram sucesso na execução cruzada de casos de teste são investigados manualmente para serem funcionalmente equivalentes. Este artigo também relata os resultados de uma avaliação de precisão de ferramentas de detecção de clones de código usando o conjunto de dados construído. O objetivo desta avaliação é avaliar com que precisão as ferramentas de detecção de clones de código poderiam encontrar os métodos funcionalmente equivalentes, e não avaliar a precisão da detecção de clones comuns. O conjunto de dados construído está disponível no github (https://github.com/YoshikiHigo/FEMPDataset).

Publicação
IEICE TRANSACTIONS on Information Vol.E107-D No.6 pp.751-760
Data de publicação
2024/06/01
Publicitada
2024/02/21
ISSN online
1745-1361
DOI
10.1587/transinf.2023EDP7268
Tipo de Manuscrito
PAPER
Categoria
Sistema de Software

1. Introdução

As linguagens de programação atuais possuem uma sintaxe rica e há muitas maneiras de os desenvolvedores implementarem as funcionalidades de que precisam. Por exemplo, no caso de Java, for declaração, o enquanto declaração, funções recursivas, Corrente, etc. podem ser usados ​​para realizar processamento repetitivo. Nos padrões de refatoração propostos por Fowler [1], as implementações antes e depois da refatoração possuem o mesmo comportamento externo, o que significa que a refatoração pode ser considerada como uma mudança de implementação de uma funcionalidade. Assim, existem inúmeras maneiras de implementar uma determinada funcionalidade, e os desenvolvedores implementam a funcionalidade necessária de acordo com suas próprias preferências e/ou políticas de seu projeto de desenvolvimento de software.

Os autores acreditam que existe uma grande quantidade de código-fonte com a mesma funcionalidade, mas estruturas diferentes em software de código aberto (doravante denominado Código SFDS1), que pode ser um conjunto de dados útil para diversos estudos em engenharia de software. Por exemplo, o código SFDS pode ser usado para avaliar ferramentas de detecção de clones de código. Como é desejável que o código-fonte que implementa a mesma funcionalidade seja detectado como clones de código, o desempenho das ferramentas de detecção de clones de código pode ser avaliado examinando o grau em que o código SFDS é detectado como clones de código. Além disso, usando o código SFDS, podemos investigar quais implementações são superiores em termos de desempenho de execução, como uso de memória e velocidade de execução, e quais implementações são superiores em termos de qualidade de software, como ISO/IEC 25010 [2].

No entanto, não é fácil identificar e coletar o código SFDS. Não é realista encontrar manualmente o código SFDS em software de código aberto e, se as ferramentas existentes de detecção de clones de código forem usadas, apenas o código SFDS que puder ser detectado pelas ferramentas existentes de detecção de clones de código será coletado. Portanto, o código SFDS coletado dessa forma não pode ser usado para avaliar ferramentas de detecção de clones de código.

Neste estudo, o código SFDS a ser coletado está limitado a pares de métodos que retornam a mesma saída (valor de retorno) quando as mesmas entradas (argumentos) são fornecidas (doravante, Métodos FE2). A ideia chave deste estudo é obter automaticamente pares candidatos de métodos FE usando uma técnica automatizada de geração de testes, EvoSuite limitando a detecção do código SFDS à detecção de métodos FE. Os candidatos obtidos de pares de métodos FE são verificados manualmente como sendo verdadeiramente equivalentes funcionalmente.

Neste estudo, selecionamos Conjunto de dados IJA [3] como alvo para detectar pares de métodos FE em Java. Conjunto de dados IJA consiste em aproximadamente 2.74 milhões de arquivos fonte (um total de aproximadamente 314 milhões de linhas de código fonte) e inclui aproximadamente 23 milhões de métodos. A partir deste conjunto de dados, 13,710 pares de métodos FE candidatos foram detectados automaticamente, dos quais 2,194 foram investigados visualmente. Como resultado, um conjunto de dados de 1,342 pares de métodos FE foi construído. Nosso conjunto de dados também inclui 852 pares de métodos que foram determinados como não sendo funcionalmente equivalentes por inspeção visual. O conjunto de dados construído está disponível em GitHub3.

Também avaliamos ferramentas de detecção de clones de código usando o conjunto de dados construído. Como resultado, descobrimos que existem muitos pares de métodos FE que não podem ser detectados pela técnica de detecção de clones baseada em token, e que as técnicas de detecção baseadas em árvores de sintaxe abstratas e aprendizado profundo têm uma forte tendência a detectar incorretamente pares de métodos que são funcionalmente inequivalente.

2. Definição de Métodos FE

Neste estudo, dois métodos são considerados funcionalmente equivalentes se retornarem a mesma saída (valor de retorno) quando as mesmas entradas (argumentos) forem fornecidas. Muitas técnicas de detecção de clones de código medem a similaridade do código-fonte dos métodos alvo para determiná-los como clones de código [4]-[6], mas este estudo não usa tal similaridade de código para determinar se determinados dois métodos são funcionalmente equivalentes ou não . Existem também técnicas que determinam clones de código usando o estado de processamento (estado da memória principal) dos métodos alvo, executando-os [7], mas este estudo não usa tal processo de cálculo para determinar se determinados dois métodos são funcionalmente equivalentes ou não.

Na pesquisa de clones de código, os clones de código detectados são frequentemente classificados de acordo com sua similaridade, como segue.

  • Digite 1  Os trechos de código são totalmente idênticos, exceto por alterações que possam existir nos espaços em branco e comentários.
  • Digite 2  A estrutura dos trechos de código é a mesma, enquanto os nomes, tipos, espaços em branco e comentários dos identificadores são diferentes.
  • Digite 3  Além de alterações em identificadores, nomes de variáveis, tipos de dados e comentários, algumas partes do código podem ser excluídas ou atualizadas, ou algumas novas partes podem ser adicionadas.
  • Digite 4  Dois trechos de código possuem textos diferentes, mas a mesma funcionalidade.

Os métodos FE detectados neste estudo são clones de código de uma parte do Tipo 4 de acordo com a classificação acima.

3. Ideia-chave para identificar automaticamente pares de métodos FE candidatos

Neste estudo, coletamos automaticamente pares candidatos de métodos FE usando os recursos estáticos (assinaturas de método) e comportamento dinâmico (resultados de teste) de Java métodos. Se os pares de métodos FE candidatos obtidos são ou não verdadeiramente equivalentes funcionalmente, é investigado manualmente. Portanto, é importante coletar automaticamente o maior número possível de pares de métodos FE candidatos.

As características estáticas do Java os métodos usados ​​​​neste estudo são o tipo de valor de retorno e os tipos de parâmetro. Como primeira etapa na obtenção de pares de métodos FE candidatos, os métodos com o mesmo tipo de valor de retorno e tipos de parâmetros são classificados no mesmo grupo. Não consideramos lançar exceções como parte de recursos estáticos, pois lançar ou não uma exceção pode ser verificado como comportamento dinâmico.

O comportamento dinâmico do Java método utilizado neste estudo é o resultado (sucesso/falha) da execução de um determinado caso de teste. Os casos de teste são gerados a partir de todos os métodos do mesmo grupo usando uma técnica automatizada de geração de testes, EvoSuite. Os casos de teste gerados por técnicas automatizadas de geração de teste têm a propriedade de que os casos de teste sempre são bem-sucedidos. Para cada par de métodos, os casos de teste gerados são executados entre si para determinar automaticamente se o par de métodos tem o mesmo comportamento. A ideia chave desta pesquisa é que se o método A for bem sucedido em todos os testes gerados a partir do método B e o método B for bem sucedido em todos os testes gerados a partir do método A, então o comportamento dos métodos A e B são equivalentes até certo ponto e suas funções podem ser equivalentes. .

Com base nesta ideia-chave, um conjunto de dados de pares de métodos FE é construído obtendo automaticamente pares de métodos de uma grande quantidade de software de código aberto que foram executados com sucesso para testes cruzados e investigação visual deles. Embora métodos com código-fonte idêntico ou semelhante possam ser funcionalmente equivalentes, tais métodos podem ser detectados por ferramentas existentes de detecção de clones de código [8]. O objetivo deste estudo é construir um conjunto de dados de pares de métodos FE que não são semelhantes no código-fonte.

4. Procedimento de construção do conjunto de dados

Neste estudo, o procedimento a seguir é usado para construir um conjunto de dados de pares de métodos FE.

  • STEP-1  classificar os métodos incluídos nos projetos alvo.
  • STEP-2  gerando casos de teste de cada método.
  • STEP-3  executar casos de teste em relação ao outro método do par para obter pares de métodos FE candidatos.
  • STEP-4  navegar no código-fonte de cada par de métodos FE candidato para determinar se o par é realmente funcionalmente equivalente.

A Figura 1 mostra uma visão geral do procedimento de construção acima. STEP-1 NFT`s STEP-3 são realizadas automaticamente através de uma ferramenta que desenvolvemos, e somente STEP-4 é realizada manualmente. Os detalhes de cada etapa são descritos abaixo.

FIG. 1  Etapas para obter pares funcionalmente equivalentes Java métodos

4.1 PASSO-1

STEP-1 analisa o código-fonte dos projetos de destino para extrair métodos e classifica os métodos extraídos com base em seu tipo de valor de retorno e tipos de parâmetro. Ao extrair métodos, as seguintes informações são recuperadas para cada método e registradas no banco de dados.

  • nome do método,
  • tipo de valor de retorno e tipos de parâmetro,
  • código-fonte (original),
  • código-fonte normalizado,
  • o número de declarações e predicados condicionais,
  • caminho de arquivo,
  • linha inicial e linha final.

No código-fonte normalizado, todos os nomes de variáveis ​​foram renomeados para nomes especiais. Um exemplo de normalização é mostrado na Fig. 2 (b). Essa normalização permite que um grupo de métodos que possuem a mesma estrutura, mas diferem apenas nas variáveis, sejam tratados como um único método. Essa normalização elimina a necessidade de tratar cada método que possui a mesma estrutura, mas difere apenas nas variáveis ​​individualmente após STEP-2, permitindo um processamento mais eficiente.

FIG. 2  Exemplo de processamento do código-fonte do método de destino

Nem todos os métodos existentes no projeto de destino são extraídos. Neste estudo, métodos com as seguintes características não são considerados para extração.

  • Métodos incluindo tipos de referência definidos em nenhum java.lang nem java.util em seu valor de retorno, parâmetros ou corpos de método.
  • Métodos cujo tipo de retorno é anular.
  • Métodos incluindo apenas uma única instrução de programa.

A razão para usar a primeira condição é que no caso de usar tipos de referência que não estão no java.lang pacote, é necessário escrever importar instruções no início do arquivo de origem ou para escrever os tipos de referência por seus nomes completos. Além disso, se o tipo de referência não estiver incluído na norma Java biblioteca, é necessário preparar seu arquivo de classe (copo arquivo), o que requer preparação adicional de compilação. A razão pela qual os tipos de referência incluídos no java.util pacote são considerados métodos de extração porque tipos frequentemente usados, como java.util.List e java.util.Set estão incluídos neste pacote. Os autores acreditam que o tratamento desses tipos de referência no java.util pacote aumentará drasticamente o número de métodos extraídos.

A razão para usar a segunda condição é que é difícil determinar automaticamente qual valor dentro de um método é o resultado final do cálculo do método para um método cujo valor de retorno é anular. Se o tipo de retorno não for anular, o valor de retorno do método pode ser considerado o resultado final do cálculo do método.

A terceira condição é usada porque o código fonte do Java contém muitos setters e getters que possuem apenas uma única instrução de programa e são inadequados como alvos para a detecção de código SFDS.

A classificação dos métodos extraídos é baseada no tipo de valor de retorno e nos tipos de parâmetros dos métodos. Métodos que possuem exatamente o mesmo tipo de retorno e tipos de parâmetro são classificados no mesmo grupo. Após a classificação de todos os métodos, se houver vários métodos em cada grupo com exatamente o mesmo código-fonte normalizado, apenas um deles será retido no grupo. A razão para isso é que não há dúvida de que métodos com código idêntico têm o mesmo comportamento, e a detecção de tais pares de métodos com a mesma implementação não é apropriada para o propósito deste estudo. Observe que grupos constituídos por apenas um único método não estão sujeitos a processamento após STEP-2.

4.2 PASSO-2

In STEP-2, cada método é cortado em um arquivo e seus casos de teste são gerados. O processamento a seguir é executado quando os métodos são cortados em arquivos.

  • Inserir 'importe java.util.*;' no início do arquivo. Isso permite a compilação mesmo se o método de destino usar uma classe no 'java.util' pacote.
  • Coloque o destino com uma declaração de classe. Atualmente, o nome da classe 'Alvo' é usado. O nome do método de destino também é alterado para '__alvo__'. Isto é para garantir o tratamento uniforme de todos os métodos alvo nos scripts criados pelos autores.
  • Remova anotações e 'estático'da assinatura do método alvo. Isso também é feito para garantir que todos os métodos de destino sejam tratados uniformemente no script.

A Figura 2 (c) mostra o código-fonte do método da Figura 2 (a) depois de ter sido cortado em um arquivo. A partir desta figura, pode-se ver que o arquivo contém apenas o método de destino, os nomes das classes e métodos são unificados e as anotações e estático modificadores anexados às assinaturas do método são removidos.

A seguir, são gerados casos de teste para cada método cortado em arquivos. Embora usemos EvoSuite [9] para gerar casos de teste, outras ferramentas de geração de teste, como Randoop [10] e Shake [11] também pode ser usado. Neste experimento, se cinco ou mais casos de teste fossem gerados a partir de um método, o método era usado em STEP-3. A razão para esta restrição é que EvoSuite pode não ser capaz de gerar casos de teste suficientes dependendo da estrutura do método de destino. Consideramos que, se não fosse possível gerar casos de teste suficientes, seria inapropriado usar tais casos de teste insuficientes para detectar candidatos a pares de métodos funcionalmente equivalentes.

Os arquivos dos quais cada método é extraído são compilados individualmente antes EvoSuite É executado. Como cada arquivo inclui apenas um único método, a compilação falhará se o método usar um campo de classe ou chamar outros métodos que foram originalmente definidos na mesma classe. EvoSuite não é executado para métodos que não conseguem compilar.

In STEP-1, métodos sem parâmetros não são explicitamente excluídos, mas métodos onde cinco ou mais casos de teste não são gerados são excluídos em STEP-2. Como não são gerados mais de cinco casos de teste a partir de um método sem parâmetros, todos os métodos sem parâmetros são excluídos. STEP-2.

4.3 PASSO-3

In STEP-3, os testes são executados mutuamente para cada método que pertence ao mesmo grupo e gerou com sucesso cinco ou mais casos de teste. Na Figura 1(c), os casos de teste são executados entre si por três métodos: Método-A, Método-B e Método-C. Método-A tem sucesso em todos os casos de teste gerados por Método-B e Método-B também é bem-sucedido em todos os casos de teste gerados por Método-A. Portanto, Método-A e Método-B são candidatos a pares de métodos funcionalmente equivalentes. Método-C não teve sucesso em um dos casos de teste gerados a partir Método-A, e não teve sucesso em todos os casos de teste gerados a partir Método-B. Portanto, o par de Método-A e Método-C, e o par de Método-B e Método-C não são candidatos a pares de métodos funcionalmente equivalentes.

4.4 PASSO-4

STEP-4 verifica visualmente o código-fonte dos pares de métodos funcionalmente equivalentes candidatos obtidos com STEP-3 para ver se eles são realmente pares de métodos com o mesmo comportamento.

5. Conjunto de dados FEMP

Nesta seção, descrevemos o conjunto de dados construído (doravante denominado FEMP conjunto de dados4). O FEMP conjunto de dados foi construído para o código-fonte incluído em Conjunto de dados IJA [3]. Conjunto de dados IJA consiste em aproximadamente 2.74 milhões de arquivos fonte, totalizando 314 milhões de linhas de código fonte, e contém aproximadamente 23 milhões de métodos. Em STEP-1, foram extraídos 257,012 métodos e classificados em 14,030 grupos. Em STEP-2, cinco ou mais casos de teste foram gerados com sucesso a partir de 27,759 métodos. Em STEP-3, obtivemos 13,710 pares de métodos candidatos funcionalmente equivalentes.

A verificação visual em STEP-4 foi realizado por três alunos do curso de mestrado pertencentes à Escola de Pós-Graduação em Ciência e Tecnologia da Informação da Universidade de Osaka. Os três alunos tinham experiência em programação utilizando Java. Primeiro, os três alunos visualizaram individualmente o código-fonte de cada par de candidatos e julgaram se eram equivalentes ou não. Em seguida, os três alunos discutiram cada par de candidatos que avaliaram de forma diferente, para determinar se eram funcionalmente equivalentes ou não.

No entanto, como não é realista verificar visualmente todos os 13,710 pares de métodos obtidos no STEP-3, o seguinte procedimento foi usado para extrair uma parte deles.

  1. Inicialize o par de métodos de destino \(P\) e o conjunto de métodos \(M\) in \(P\) como vazio, respectivamente.
  2. Organize os 13,710 pares de métodos em ordem crescente por ID5e execute os seguintes processos em ordem.
    • Se ambos os métodos que compõem o par de métodos não estiverem incluídos no \(M\), o par de métodos é adicionado a \(P\) e ambos os métodos são adicionados a \(M\).
    • Se pelo menos um método compreendendo o par de métodos estiver contido em \(M\), nada é feito.

Após o procedimento acima, 2,194 pares de métodos foram incluídos no \(P\). Todos esses 2,194 pares de métodos consistiam em métodos diferentes. Para esses 2,194 pares de métodos, cada aluno levou 44 horas e 48 minutos, 33 horas e 19 minutos e 43 horas e 25 minutos, respectivamente, para determinar se eram funcionalmente equivalentes ou não. Posteriormente, a discussão de cada par de métodos, para o qual foi dividida a avaliação, durou 9 horas e 28 minutos no total.

STEP-4 resultou em 1,342 dos 2,194 pares de métodos sendo determinados como funcionalmente equivalentes, com os 852 restantes não sendo funcionalmente equivalentes. O número de pares de métodos discutidos por três alunos com avaliações diferentes foi 296. Este conjunto de dados está disponível no github6.

A Figura 3 é um exemplo de um par de métodos que foi determinado como funcionalmente equivalente em STEP-4. Ambos os métodos implementam a função de retornar o menor valor entre os três valores duplos dados como parâmetros. O método minutos implementa esta função apenas usando o if-instrução, enquanto o método mínimo implementa-o usando o if-instrução e o operador ternário. Por outro lado, a Fig. 4 é um exemplo de um par de métodos cujas funções foram determinadas como não equivalentes em STEP-4. Ambos os métodos determinam a equivalência de duas matrizes bidimensionais fornecidas como parâmetros. A funcionalidade difere porque o método ArrayEquals Retorna falso se um array vazio for fornecido, enquanto o método é igual a Retorna verdadeiro se uma matriz vazia for fornecida. EvoSuite gerou nove casos de teste para o método ArrayEquals e oito casos de teste para o método é igual a, mas nenhum caso de teste foi gerado para encontrar as diferenças funcionais entre os dois métodos7.

FIG. 3  Exemplo de par de métodos funcionalmente equivalente

FIG. 4  Exemplo de par de métodos funcionalmente inequivalentes

A seguir, descrevemos as características das assinaturas dos métodos no FEMP conjunto de dados. Os 1,342 pares de métodos funcionalmente equivalentes consistem em 468 assinaturas, e os 852 pares de métodos funcionalmente não equivalentes consistem em 338 assinaturas. No conjunto de dados, 713 (= 53.1%) pares de métodos funcionalmente equivalentes e 317 (= 37.2%) pares de métodos funcionalmente não equivalentes incluem apenas tipos primitivos, como int e carbonizar em seu tipo de valor de retorno e tipos de parâmetro. A Tabela 1 mostra as 10 assinaturas mais frequentes de pares de métodos funcionalmente equivalentes e funcionalmente não equivalentes no FEMP conjunto de dados. Esta tabela também mostra que os pares de métodos funcionalmente equivalentes tendem a ser compostos apenas por tipos primitivos. Este fato significa que a proporção de pares de métodos que são determinados como funcionalmente desiguais na construção do conjunto de dados STEP-4 é maior quando tipos não primitivos são incluídos nas assinaturas. Isto indica que é mais difícil gerar casos de teste suficientes quando tipos não primitivos são incluídos na assinatura do que quando apenas tipos primitivos são incluídos.

tabela 1  As 10 principais assinaturas de pares de métodos funcionalmente equivalentes e inequivalentes

6. Avaliação de precisão de ferramentas de detecção de clones

Aqui, descrevemos os resultados de uma avaliação de precisão de ferramentas de detecção de clones como um exemplo de utilização do FEMP conjunto de dados. O objetivo desta avaliação é avaliar com que precisão as ferramentas de detecção de clones de código poderiam encontrar os métodos funcionalmente equivalentes, e não avaliar a precisão da detecção de clones comuns. Nesta avaliação, os 1,342 pares de métodos determinados como funcionalmente equivalentes em STEP-4 devem ser detectados como pares de clones, e os 852 pares de métodos determinados como não sendo funcionalmente equivalentes não devem ser detectados como pares de clones. O primeiro conjunto é chamado \(\mathit{EMP}~(Equivalent~Method~Pairs)\) e o último conjunto é chamado \(\mathit{IMP}~(Inequivalent~Method~Pairs)\).

6.1 Ferramentas de detecção de clones a serem avaliadas

Três ferramentas de detecção de clones foram alvo desta avaliação: NIL [12], InferCode [13] e ASTNN [14].

NIL identifica rapidamente possíveis pares de métodos candidatos a clones usando o índice invertido e N-grama da sequência lexical obtida do código-fonte alvo. Ele aplica o algoritmo de subsequência comum mais longa a esses candidatos para determinar se eles são pares de clones ou não. NIL é uma ferramenta para detectar grande variação clones, que são difíceis de detectar usando técnicas convencionais de detecção de clones. Na comparação com outras ferramentas de detecção de clones LVMapper [15] e CCAligner [16] realizado em dois sistemas de código aberto, o número de grande variação clones detectados por NIL foi 354 e 398 (precisões de 86% e 88%), enquanto LVMapper detectou 355 e 389 (64% e 60% de precisão) e CCAligner detectou 184 e 284 (43% e 49% de precisão).

InferCode é um modelo de pré-treinamento que usa uma rede neural convolucional [17] baseada em árvores sintáticas abstratas e estruturas em árvore. Ele pode ser usado para tarefas de aprendizagem não supervisionadas, como agrupamento de código-fonte, e tarefas de aprendizagem supervisionadas, como classificação de código-fonte. Bui et al. implementaram a detecção de clones em InferCode como uma tarefa de aprendizagem não supervisionada. Nesta comparação usamos InferCode como uma técnica de detecção de clones baseada em aprendizagem não supervisionada. A detecção de clones usa similaridade de cosseno como semelhança entre os dois métodos. Bui et al. estabeleceu um limite de 0.8 para que a similaridade do cosseno fosse considerada como um par de clones e conduziu experimentos em BigCloneBench [18] e OJClone [19]. Para BigCloneBench [18], a precisão e recall foram de 90% e 56%, respectivamente, e para OJClone [19], a precisão e a recuperação foram de 61% e 70%, respectivamente.

ASTNN é um modelo baseado em árvores de sintaxe abstratas e redes neurais de regressão. Ele aprende informações lexicais contidas no código-fonte de destino e informações sintáticas por instrução do programa. Para detecção de clones, ASTNN gera um valor entre 0 e 1. Dois métodos de entrada são determinados como um par de clones se esse valor for maior ou igual a um valor limite. Zhang et al. experimentou em BigCloneBench e OJClone com um valor limite de 0.5. Para OJClone, a precisão e a evocação foram de 98.9% e 92.7%, respectivamente. Para BigCloneBench, a precisão da detecção foi avaliada para cada categoria de clone. Os resultados mostraram que para Weakly Type-3/Type-4, que são clones com similaridade sintática inferior a 50%, a precisão e a recuperação foram de 99.8% e 88.3%, respectivamente.

Nos jornais de NIL, InferCode e ASTNN ([12]-[14]), essas ferramentas são avaliadas usando BigCloneBench [18] e OJClone [19]. BigCloneBench categoriza todas as funções em uma das 43 categorias diferentes e então assume que todos os métodos atribuídos a uma funcionalidade também são clones uns dos outros. Os métodos não são funcionalmente equivalentes e isto não é reivindicado. Também, OJClone é um conjunto de dados construído a partir de código de programação competitivo, de natureza diferente do código incluído no OSS.

6.2 Como detectar clones

Aqui explicamos como configuramos as três ferramentas para detectar clones de código.

Nós instalamos NIL de acordo com as instruções em GitHub8 of NIL. A detecção de clones foi realizada gerando cada método em \(\mathit{EMP}\) e \(\mathit{IMP}\) como um arquivo separado e fornecendo esses dois arquivos para NIL como alvos de detecção de clones. Em outras palavras, corremos NIL 2,194 vezes (1,342 vezes para \(\mathit{EMP}\) e 852 vezes para \(\mathit{IMP}\)). Como alguns métodos são pequenos, o número mínimo de linhas e o número mínimo de tokens para um método ser detectado como um clone foram definidos como 19.

Nós instalamos InferCode de acordo com as instruções fornecidas em GitHub10 of InferCode. Nós costumavamos InferCode para obter dados vetoriais para cada método em \(\mathit{EMP}\) e \(\mathit{IMP}\)e detectou clones alterando o limite da similaridade de cosseno dos pares de métodos de 0 para 1 em etapas de 0.001.

Obtivemos um modelo pré-treinado de ASTNN de acordo com a descrição em ASTNN'S GitHub11. A seguir, os 1,342 pares de métodos em \(\mathit{EMP}\) foram divididos em 10 blocos. Os blocos foram classificados de forma que a proporção de dados de ajuste fino, validação e teste fosse de 8:1:1, e a detecção de clones usando ASTNN foi realizado para que todos os blocos já fossem dados de teste. Desde a saída de ASTNN é um número entre 0 e 1, o limite para ser um clone variou de 0 a 1 em incrementos de 0.001 e os resultados foram avaliados12.

6.3 Medidas de Avaliação para Resultados de Detecção de Clones

Três medidas, \(recall^{E}(t)\), \(recall^{I}(t)\) e \(accuracy(t)\), foram usados ​​para avaliar os resultados de detecção de clones da ferramenta \(t\) nesta avaliação. Primeiro, as definições de \(\mathit{EMP}(t)\) e \(\mathit{IMP}(t)\) usados ​​nessas medidas de avaliação são os seguintes.

  • \(\mathit{EMP}(t)\) um conjunto de pares de métodos em \(\mathit{EMP}\) que foram corretamente determinados como funcionalmente equivalentes (detectados como clones) pela ferramenta de detecção \(t\).
    \(\mathit{IMP}(t)\) um conjunto de pares de métodos em \(\mathit{IMP}\) cujas funções são corretamente determinadas como não sendo funcionalmente equivalentes pela ferramenta de detecção \(t\) (não detectado como clones).

Usando as definições acima, definimos \(accuracy(t)\), \(recall^{E}(t)\) e \(recall^{I}(t)\) do seguinte modo. Observe que \(|A|\) denota o número de elementos no conjunto \(A\).

\[\begin{aligned} & recall^{E}(t) = \frac{|\mathit{EMP}(t)|}{|\mathit{EMP}|} \\ & recall^{I}(t) = \frac{|\mathit{IMP}(t)|}{|\mathit{IMP}|} \\ & accuracy(t) = \frac{|\mathit{EMP}(t)|+|\mathit{IMP}(t)|}{|\mathit{EMP}|+|\mathit{IMP}|} \end{aligned}\]

6.4 Resultados de Detecção

Os resultados de detecção de NIL são mostrados na Tabela 2. O \(recall^{E}(\mathit{NIL})\) foi de 34.5% (=463/1,342), \(recall^{I}(\mathit{NIL})\) foi de 72.54% (=618/852), e \(accuracy(\mathit{NIL})\) foi de 49.27% (=1,081/2,194). Estes resultados indicam que a detecção de clones por NIL tem muitas omissões na busca de métodos funcionalmente equivalentes e também inclui alguns falsos positivos.

tabela 2  Resultados de detecção de NIL

Os resultados da InferCode avaliação são mostradas na Fig. 5 (a). Quando o limite é 0.557 ou menos, \(recall^{E}(\mathit{InferCode})\) é superior a 99%, mas \(recall^{I}(\mathit{InferCode})\) é inferior a 0.35% ao mesmo tempo. Em outras palavras, quase todos os pares de métodos funcionalmente equivalentes são detectados como clones, mas quase todos os pares de métodos funcionalmente não equivalentes também são detectados como clones. Aumentar o valor limite melhora \(recall^{I}(\mathit{InferCode})\), mas piora \(recall^{E}(\mathit{InferCode})\) ao mesmo tempo. O valor de \(accuracy(\mathit{InferCode})\) foi o mais alto quando o valor limite foi de 0.949, que foi de 64.04%. Neste momento, \(recall^{E}(\mathit{InferCode})\) foi de 83.83% e \(recall^{I}(\mathit{InferCode})\) foi 32.86%.

FIG. 5  Precisão de detecção versus limite. O eixo Y representa uma porcentagem no intervalo de 0 a 100. Para o eixo X, a extremidade esquerda do eixo horizontal representa um limite de 0 e a extremidade direita um limite de 1.

Os resultados da avaliação de ASTNN são mostrados na Fig. 5 (b). No geral, a forma do gráfico de ASTNN é semelhante ao de InferCode. Para limites abaixo de 0.531, \(recall^{E}(\mathit{ASTNN})\) é superior a 99%, enquanto \(recall^{I}(\mathit{ASTNN})\) é de apenas 0.59% ao mesmo tempo. Nos valores limite de 0.677\(\sim\)0.681, \(arrucary(\mathit{ASTNN})\) tem o maior valor de 61.30%, no qual \(recall^{E}(\mathit{ASTNN})\) e \(recall^{I}(\mathit{ASTNN})\) apresentam valores de 94.19% e 9.62%, respectivamente.

Descobrimos que a ferramenta de detecção de clones NIL, que é baseado em sequências lexicais, não consegue detectar muitos pares de métodos funcionalmente equivalentes como clones e não possui uma alta capacidade de detectar métodos funcionalmente equivalentes. Também descobrimos que InferCode e ASTNN, ferramentas de detecção de clones baseadas em árvores de sintaxe abstratas e aprendizado profundo, podem detectar pares de métodos funcionalmente equivalentes como clones, mas também detectam métodos funcionalmente inequivalentes como clones. A partir dos resultados acima, concluímos que novos métodos precisam ser desenvolvidos para encontrar adequadamente pares de métodos funcionalmente equivalentes.

7. Trabalho Relacionado

Esta pesquisa é inspirada na literatura [20]. Na literatura é apresentada a ideia de obter um conjunto de métodos funcionalmente equivalentes executando os casos de teste gerados entre si13, e um conjunto de dados de conjuntos de métodos funcionalmente equivalentes foi construído a partir do conjunto de dados de Borge [21]. As diferenças entre este artigo e a literatura são as seguintes.

  • O conjunto de dados de Borge [21] inclui aproximadamente 36 milhões de linhas de código, enquanto o Conjunto de dados IJA usado neste artigo tem aproximadamente 314 milhões de linhas de código. Há também uma diferença no tamanho dos conjuntos de dados construídos: o conjunto de dados construído na literatura [20] inclui 276 conjuntos de métodos funcionalmente equivalentes, enquanto o conjunto de dados neste artigo contém 1,342 pares de métodos funcionalmente equivalentes.
  • Embora todos os métodos capazes de gerar testes estivessem sujeitos à execução de testes na literatura [20], neste artigo, a execução de testes não foi realizada quando o número de casos de testes gerados era inferior a cinco. A razão para isso é que no processo de construção do conjunto de dados da literatura [20], quando o número de testes gerados era pequeno, na maioria dos casos os métodos foram considerados não funcionalmente equivalentes pelo olho humano, mesmo que a execução mútua de casos de teste foram bem-sucedidos.
  • No processo de construção do conjunto de dados, as verificações visuais foram realizadas por um autor da literatura [20], enquanto no processo de construção do conjunto de dados neste artigo, a decisão final sobre se as funções são equivalentes foi tomada após avaliação independente e discussão por três pessoas.
  • Este artigo avalia três ferramentas de detecção de clones de código como um exemplo do uso do conjunto de dados construído, mas nenhum caso de uso é fornecido na literatura [20].

Svajlenko et al. construiu o BigCloneBench conjunto de dados [22]. Existem apenas 43 funcionalidades diferentes no atual BigCloneBench versão. Ao final do procedimento de construção do conjunto de dados, foi realizada a validação manual. Contudo, o alvo do trabalho de validação humana é a Java métodos descobertos por palavras-chave e padrões de código. Portanto, métodos funcionalmente equivalentes que não são encontrados por palavras-chave e padrões de código não são incluídos no BigCloneBench conjunto de dados. Além disso, os métodos alvo não foram executados durante o procedimento de construção do conjunto de dados e nenhuma verificação de equivalência funcional foi realizada a partir de uma perspectiva dinâmica.

Liu et al. construiu um conjunto de dados de programas funcionalmente equivalentes usando dados de competições de programação anteriores. Eles coletaram programas funcionalmente equivalentes para cerca de 5,000 questões [23]. Neste conjunto de dados, os programas desenvolvidos por vários usuários para uma questão são tratados como programas funcionalmente equivalentes. Zhao et al. publicar um conjunto de dados de programas com a mesma funcionalidade em Google Code Jam [19] e Mou et al. publicar também um conjunto de dados de programas submetidos à programação de sistemas de apoio à educação [17]. Por outro lado, ao contrário dos seus conjuntos de dados, o nosso conjunto de dados não é um programa para programação competitiva, mas sim código-fonte com características funcionalmente equivalentes incluídas no OSS.

Rabin et al. desenvolveram uma ferramenta, ProgramaTransformador, que altera a estrutura de um determinado programa [24]. A ferramenta possui uma série de regras para alterar a estrutura de um programa e altera a estrutura com base nessas regras. Por exemplo, ele reescreve automaticamente as repetições descritas por for-declarações em enquanto-statements e altera nomes de variáveis.

8. Ameaças à validade

Aqui, descrevemos os fios de validade nesta pesquisa.

8.1 Normalização de Código

A normalização em STEP-1 impede o procedimento proposto na Seção. 4 da saída de clones Tipo 1 e Tipo 2 como pares de métodos funcionalmente equivalentes. Essa normalização também reduz consideravelmente o número de métodos direcionados após STEP-2, o que melhora consideravelmente a velocidade geral de processamento do procedimento proposto.

No entanto, há um aspecto negativo nesta normalização. A Figura 6 mostra dois métodos artificiais que terminam exatamente no mesmo código-fonte devido à normalização. Esses métodos não são clones simples do Tipo 2 porque executam operações semanticamente diferentes. Portanto, esses métodos podem ser incluídos no conjunto de dados construído neste estudo. No entanto, como os códigos-fonte desses dois métodos são exatamente os mesmos após a normalização, um dos dois métodos será removido em STEP-1 se ambos existirem no código-fonte de destino. O procedimento proposto na Seção. 4 é uma maneira de construir um grande conjunto de dados da maneira mais eficiente possível e não detecta todos os métodos funcionalmente equivalentes que existem no código-fonte de destino. Portanto, não é um grande problema ignorar esses métodos de casos extremos.

FIG. 6  Um exemplo artificial de dois métodos que são processados ​​semanticamente de forma diferente, embora a normalização em STEP-1 resulta exatamente no mesmo código-fonte para eles.

8.2 Julgamento Humano

In STEP-4, julgamentos humanos se os pares de métodos alvo são verdadeiramente funcionalmente equivalentes ou não. Como os julgamentos foram feitos por humanos, não foi possível eliminar completamente a subjetividade, e a possibilidade de erros de julgamento não pode ser negada. Para minimizar ao máximo essas possibilidades, esta pesquisa decidiu obter consenso entre três pessoas em vez de duas.

9. Conclusão

Neste estudo, identificamos pares de métodos funcionalmente equivalentes gerando automaticamente casos de teste para Java métodos extraídos de software de código aberto e executando os casos de teste gerados entre si. Pares de métodos funcionalmente equivalentes foram extraídos dos 314 milhões de linhas de Java código-fonte incluído no Conjunto de dados IJA conjunto de dados. Como resultado, obtivemos 13,710 pares de métodos candidatos funcionalmente equivalentes. Destes, 2,194 pares de métodos foram verificados visualmente e 1,342 pares de métodos funcionalmente equivalentes foram obtidos. Este estudo também usou este conjunto de dados para avaliar a precisão de três ferramentas de detecção de clones de código. Este conjunto de dados também pode ser usado para examinar a qualidade do código, como capacidade de manutenção e compreensão do código.

O desafio atual é que leva muito tempo para encontrar pares de métodos candidatos funcionalmente equivalentes, uma vez que todas as combinações de métodos com valores de retorno e tipos de parâmetros iguais que poderiam gerar testes são testadas entre si. Neste experimento, foram necessários aproximadamente 40 dias para STEP-3 sozinho. No futuro, planejamos introduzir heurísticas para reduzir o número de combinações de métodos que precisam ser executadas mutuamente, a fim de encontrar pares de métodos candidatos funcionalmente equivalentes mais rapidamente.

A grande porcentagem (852/2,194 = 38.8%) de pares de métodos que foram determinados como funcionalmente desiguais por inspeção visual também precisa ser melhorada. Se houver poucos pares de métodos que sejam determinados como funcionalmente desiguais por inspeção visual (se a execução mútua de casos de teste eliminar a maioria dos métodos que não são funcionalmente equivalentes), então a necessidade de inspeção visual seria eliminada e um grande volume de dados seria eliminado. conjunto pode ser criado quase automaticamente. Nosso objetivo é gerar testes automáticos de maior qualidade, melhorando o algoritmo de geração de testes em EvoSuite.

Agradecimentos

Esta pesquisa foi apoiada pela JSPS KAKENHI Japão (JP20H04166, JP21K18302, JP21K11829, JP21H04877, JP22H03567, JP22K11985).

Referências

[1] M. Fowler, “Refactoring: Improving the Design of Existing Code,” Addison-Wesley Longman Publishing Co., Inc., USA, 1999.
CrossRef

[2] ISO/IEC 25010, “ISO/IEC 25010:2011, systems and software engineering - systems and software quality requirements and evaluation (square) - system and software quality models,” 2011.

[3] J. Svajlenko, “Ijadataset 2.0 + bigclonebench samples.” https://1drv.ms/u/s!AhXbM6MKt_yLj_N3FAIGw3CJb1JGOg?e=NsP59Z, 2020.

[4] Q.U. Ain, W.H. Butt, M.W. Anwar, F. Azam, and B. Maqbool, “A systematic review on code clone detection,” IEEE Access, vol.7, pp.86121-86144, 2019.
CrossRef

[5] D. Rattan, R. Bhatia, and M. Singh, “Software clone detection: A systematic review,” Information and Software Technology, vol.55, no.7, pp.1165-1199, 2013.
CrossRef

[6] M. Zakeri-Nasrabadi, S. Parsa, M. Ramezani, C. Roy, and M. Ekhtiarzadeh, “A systematic literature review on source code similarity measurement and clone detection: Techniques, applications, and challenges,” Journal of Systems and Software, vol.204, p.111796, 2023.
CrossRef

[7] H. Kim, Y. Jung, S. Kim, and K. Yi, “Mecc: Memory comparison-based clone detector,” Proc. 33rd International Conference on Software Engineering, ICSE ’11, New York, NY, USA, pp.301-310, Association for Computing Machinery, 2011.
CrossRef

[8] K. Inoue and C.K. Roy, “Code Clone Analysis: Research, Tools, and Practices,” Springer, Singapore, 2021.
CrossRef

[9] Evosuite, “Evosuite: Automatic test suite generation for java,” https://www.evosuite.org/, 2021.

[10] Randoop, “Randoop: Automatic unit test generation for java.” https://randoop.github.io/randoop/, 2022.

[11] A. Technologies, “Agitarone.” http://www.agitar.com/solutions/products/agitarone.html, 2015.

[12] T. Nakagawa, Y. Higo, and S. Kusumoto, “NIL: Large-Scale Detection of Large-Variance Clones,” Proc. 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2021, pp.830-841, 2021.
CrossRef

[13] N.D.Q. Bui, Y. Yu, and L. Jiang, “Infercode: Self-supervised learning of code representations by predicting subtrees,” 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), pp.1186-1197, 2021.
CrossRef

[14] J. Zhang, X. Wang, H. Zhang, H. Sun, K. Wang, and X. Liu, “A novel neural source code representation based on abstract syntax tree,” 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pp.783-794, 2019.
CrossRef

[15] M. Wu, P. Wang, K. Yin, H. Cheng, Y. Xu, and C.K. Roy, “LVMapper: A Large-Variance Clone Detector Using Sequencing Alignment Approach,” IEEE Access, vol.8, pp.27986-27997, 2020.
CrossRef

[16] P. Wang, J. Svajlenko, Y. Wu, Y. Xu, and C.K. Roy, “CCAligner: A Token Based Large-Gap Clone Detector,” 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE), pp.1066-1077, 2018.

[17] L. Mou, G. Li, L. Zhang, T. Wang, and Z. Jin, “Convolutional neural networks over tree structures for programming language processing,” Proc. Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16, vol.30, no.1, pp.1287-1293, AAAI Press, 2016.
CrossRef

[18] J. Svajlenko, “Bigclonebench.” https://github.com/clonebench/BigCloneBench, 2022.

[19] G. Zhao and J. Huang, “Deepsim: Deep learning code functional similarity,” Proc. 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2018, New York, NY, USA, pp.141-151, Association for Computing Machinery, 2018.
CrossRef

[20] Y. Higo, S. Matsumoto, S. Kusumoto, and K. Yasuda, “Constructing dataset of functionally equivalent java methods using automated test generation techniques,” Proc. 19th International Conference on Mining Software Repositories, pp.682-686, Association for Computing Machinery, 2022.
CrossRef

[21] H. Borges, A. Hora, and M.T. Valente, “Understanding the factors that impact the popularity of github repositories,” 2016 IEEE International Conference on Software Maintenance and Evolution (ICSME), pp.334-344, IEEE, Oct. 2016.
CrossRef

[22] J. Svajlenko and C.K. Roy, “Bigcloneeval: A clone detection tool evaluation framework with bigclonebench,” 2016 IEEE International Conference on Software Maintenance and Evolution (ICSME), IEEE, pp.596-600, Oct 2016.
CrossRef

[23] H. Liu, M. Shen, J. Zhu, N. Niu, G. Li, and L. Zhang, “Deep learning based program generation from requirements text: Are we there yet?,” IEEE Trans. Softw. Eng., vol.48, no.4, pp.1268-1289, 2020.
CrossRef

[24] M.R.I. Rabin and M.A. Alipour, “Programtransformer: A tool for generating semantically equivalent transformed programs,” Software Impacts, vol.14, p.100429, 2022.
CrossRef

Notas de rodapé

1. Mesma funcionalidade, mas estruturas diferentes
2. Funcionalmente Equivalente
3. https://github.com/YoshikiHigo/FEMPDataset
4. Conjunto de dados de pares de métodos funcionalmente equivalentes
5. Os 13,710 pares de métodos obtidos no STEP-3 têm valores inteiros exclusivos como seus IDs.
6. https://github.com/YoshikiHigo/FEMPDataset
7FEMP conjunto de dados também inclui casos de teste gerados por Evosuite.
8. https://github.com/kusumotolab/NIL
9. No entanto, desde NIL é processado internamente usando N-grama fazendo o melhor dos nossos N=5, são necessárias no mínimo cinco palavras para serem detectadas como um clone.
10. https://github.com/bdqnghi/infercode
11. https://github.com/zhangj111/astnn
12. Os hiperparâmetros usados ​​para ajuste fino foram: tamanho do lote:32, epoche:5, tamanho de aprendizagem:2e-3, tamanho do vetor de word2vec:128, dimensão oculta:100, dimensão de codificação:128.
13. Na literatura [20], Higo et al. obtivemos um conjunto de métodos funcionalmente equivalentes, enquanto neste artigo determinamos a equivalência funcional por pares de métodos em vez de um conjunto.

autores

Yoshiki HIGO
  Osaka University

received his master’s degree and Ph.D degree in information science and technology from Osaka University in 2004 and 2006, respectively. At present he is a professor at Osaka University. His research interests include mining software repositories, program analysis, and automated program repair. He is a member of IEEE, IPSJ, IEICE, and JSSST.

Palavra-chave