Complexity-Based Code Embeddings

Rares Folea, Radu Cristian Alexandru Iacob, Emil Slusanschi, Traian Rebedea

Abstract

Identifying the underlying algorithm in a piece of source code—algorithmic classification—is a fundamental challenge in software analysis. Traditional static analysis methods often struggle with semantic variations where different code structures implement the same logic. This paper presents a novel dynamic analysis framework that generates "r-Complexity embeddings" based on a program's execution behavior. By measuring how hardware metrics, such as cache misses and CPU cycles, scale with input size, the system creates a unique numerical fingerprint for algorithms. Experimental results on competitive programming datasets demonstrate that this approach achieves a 90% F1-score in multi-label classification across 11 algorithmic categories.

Introduction

Algorithmic classification is essential for tasks ranging from automated grading to plagiarism detection and malware analysis. However, static analysis, which relies on source code text or Abstract Syntax Trees (ASTs), frequently fails to capture the deep semantics of a program. Two programs may appear structurally similar yet implement different algorithms, or vice versa.

To overcome these limitations, the authors propose a shift toward dynamic analysis. Instead of analyzing what the code looks like, the proposed system analyzes how the code behaves during execution. Specifically, it focuses on how hardware resource consumption scales as input size increases, treating asymptotic complexity as a robust feature for machine learning.

System Architecture

The proposed framework is divided into two primary planes: the Control Plane and the Data Pipeline Plane. The Control Plane manages scheduling, metadata, and reporting, while the Data Pipeline Plane handles the heavy lifting of code compilation, problem discovery, and metric aggregation.

The high-level system architecture of the r-Complexity pipeline, illustrating the flow from user input and crawlers through the control and data pipeline planes.

As shown in the architecture, the system utilizes several specialized databases, including TheCrowdCodeforces for solution storage and TheInputsCodeforces for synthetic test cases. The pipeline executes solutions in a dedicated environment to collect high-fidelity hardware telemetry.

Generating r-Complexity Embeddings

The core innovation of this work is the creation of r-Complexity embeddings through a multi-step dynamic profiling process.

  1. Dynamic Profiling: C++ solutions are executed against synthetic inputs of varying sizes. Using the Linux perf tool, the system collects 10 distinct metrics, including hardware events (e.g., branch-misses, CPU cycles) and software events (e.g., context-switches).
  2. Complexity Tailoring: For each metric, the system observes the growth pattern relative to input size ($n$). These observations are fitted to "Big r-Theta" functions, which provide a granular view of growth patterns such as logarithmic, polynomial, or factorial.
  3. Embedding Construction: The parameters of the best-fitting complexity functions—including feature type, intercept, and r-value—are concatenated into a 36-long numerical vector. This vector serves as the embedding for the code snippet.
The end-to-end process of generating embeddings: from source code compilation and execution against sample inputs to the extraction of hardware metrics and final complexity function fitting.

Experimental Results

The researchers evaluated the embeddings using standard machine learning models, including Random Forests and XGBoost, on a multi-label dataset of 5,949 program executions.

  • High Accuracy: In binary classification tasks (e.g., "math" vs. "non-math"), the models achieved 96-97% accuracy.
  • Robust Multi-Label Performance: For the 11-class algorithmic classification task, the XGBoost model achieved an average F1-score of 90%.
  • Precision: The system demonstrated exceptionally high precision, particularly for well-defined classes like "divide and conquer" and "binary search," where the model's predictions were almost always correct.

The results highlight that hardware telemetry, such as stalled-cycles-frontend, provides critical signals that distinguish between algorithms with similar time complexities but different execution structures, such as nested loops versus recursion.

Conclusion and Future Work

Complexity-based embeddings offer a powerful, semantics-aware alternative to static code representations. While the current approach is somewhat dependent on hardware architecture and requires manual generation of synthetic inputs, it demonstrates the viability of using execution dynamics for high-accuracy algorithmic classification. Future research will focus on automating input generation and exploring the transferability of embeddings across different hardware environments.

Summary updated

Abstract

This paper presents a generic method for transforming the source code of various algorithms to numerical embeddings, by dynamically analysing the behaviour of computer programs against different inputs and by tailoring multiple generic complexity functions for the analysed metrics. The used algorithms embeddings are based on r-Complexity . Using the proposed code embeddings, we present an implementation of the XGBoost algorithm that achieves an average F1-score on a multi-label dataset with 11 classes, built using real-world code snippets submitted for programming competitions on the Codeforces platform.
BibTeX
@inproceedings{folea2023complexity,
  author = {Rares Folea and Radu Cristian Alexandru Iacob and Emil Slusanschi and Traian Rebedea},
  title = {{Complexity-Based Code Embeddings}},
  booktitle = {ICCCI},
  year = {2023},
  doi = {10.1007/978-3-031-41456-5\_20},
}

Loading related content...

Figure