Análise de complexidade de códigos com rede neural de grafos

Abstract

A complexidade de código é uma característica diretamente relacionada ao tempo de execução de um código e a sua eficiência. Obter uma eficiência maior ou tempo de execução menor, são objetivos comuns em qualquer área na engenharia, mas esses objetivos se tornam prevalecentes na análise de sistemas de alta precisão e em aplicações de tempo real. A identificação automatizada da complexidade ou de trechos problemáticos, poderia auxiliar nesses objetivos e otimizar os processos de desenvolvimento de algoritmos, porém, no problema da parada de Alan Turing, provou-se que é impossível a criação de um método ou função genérico capaz de calcular a complexidade exata de qualquer programa. Essa barreira teórica impõe a necessidade de investigar uma diferente abordagem baseada na estimativa de complexidade. Assim, neste trabalho analisa-se a viabilidade de Redes Neurais de Grafo (GNN) para essa tarefa, implementando-se diferentes modelos e testando-os e avaliando-os sobre diferentes métricas. Desenvolveu-se o modelo \textit{ComplexityGNN}, treinado e avaliado sobre 37608 exemplos em oito linguagens, atingindo acurácia de 67{,}6\% na classificação por classe e AUC-ROC de 0,926 na classificação binária de eficiência, demonstrando a viabilidade da abordagem para estimativa de complexidade de código.

Code complexity is a characteristic directly related to the execution time and efficiency of a program. Achieving higher efficiency or shorter execution times are common objectives in any engineering field, but these goals become paramount in the analysis of high-precision systems and real-time applications. The automated identification of complexity or problematic code segments could assist in these objectives and optimize algorithm development processes. However, as demonstrated by Alan Turing's halting problem, it is theoretically impossible to create a generic method or function capable of calculating the exact complexity of any arbitrary program. This theoretical barrier imposes the need to investigate an alternative approach based on complexity estimation. Thus, this work analyzes the feasibility of Graph Neural Networks (GNN) for this task by implementing, testing, and evaluating different models across various metrics. The model \textit{ComplexityGNN} was developed, trained and tested under 37608 examples in 8 programming languages, measuring 67{,}6\% accuracy estimating by classes and AUC-ROC of 0{,}926 in binary classification of efficiency, presenting the viability of the approach of estimation of complexity.