Modification the use of the Floyd-Warshell algorithm when working with tree-structure graphs

Abstract

In modern blockchain systems, smart contracts are one of the most critical components for ensuring the automated execution of agreements without the need for intermediaries. However, smart contracts written in languages like Solidity may contain vulnerabilities that can be exploited by malicious actors to steal funds or manipulate assets. Given the increasing number of attacks on smart contracts, the development of effective methods for detecting such vulnerabilities is crucial. Traditional approaches to detecting vulnerabilities in smart contracts include symbolic execution, fuzzing, formal verification, and pattern matching. These methods have their advantages but face several challenges, such as high resource consumption, limitations in detecting new types of vulnerabilities, and difficulties in scaling to large contracts. As a result, there is a need to introduce new approaches, such as natural language processing (NLP) and machine learning, which can address these challenges more effectively. In this study, an NLP-based method was explored, using Word2Vec to convert smart contract code into vector representations, allowing for better analysis of the semantic relationships between elements of the code. These vector representations are then fed into a bidirectional recurrent neural network with GRU blocks and an attention mechanism. This approach allows the model to focus on the most important parts of the code and improve the accuracy of vulnerability detection. The comparative analysis showed that NLP-based methods significantly outperform traditional approaches in all key metrics. In particular, the GRU model with an attention mechanism demonstrated high results in accuracy, recall, and F-measure, making it effective for detecting complex vulnerabilities such as reentrancy. Furthermore, the NLP-based approach is capable of adapting to new types of attacks thanks to training on large datasets. Thus, the integration of NLP and machine learning represents a promising direction for enhancing the security of smart contracts. Future research can focus on improving these approaches, particularly through the implementation of advanced models such as transformers. An integral part of any software project is the use of algorithms. Algorithms, which are the canvas, the basis of a large number of software solutions, are classical, printed in programmer's notebooks and often implemented in many programming languages. But any software project has many subtleties that cannot be exhausted by the classical approach, searches for ready-made solutions according to given parameters are also unsuccessful, or ready-made functions do not meet the given criteria of speed or accuracy. An example of such an algorithm, the solution of which is proposed in this work, is an algorithm for finding all minimum distances between any two vertices on a tree-structure graph. The Floyd-Warshall algorithm, universal, created for a graph of any structure, cyclic or directed, was used as the basis for its writing. The work proves that the tree structure of a graph is much simpler than a generalized cyclic structure, where the links can be edges or arcs. The work shows that in a tree there is only one path between any two vertices, that is, we do not have any need to recalculate the received answer - the distance between two specific vertices, hoping that it will be more optimal according to the criteria of the task, so we can get rid of a huge number of conditional operators and an outer loop, the number of iterations of which corresponds to the number of vertices, that is, if in a typical project the number of vertices of a tree-structure graph starts from a thousand vertices, then using the modified Floyd algorithm specifically for treestructure graphs, and not the widespread, so-called, universal version, it is possible to speed up the work of the software product by at least a thousand times. In addition, tree-structure graphs have a number of structural differences that allow for another two to ten times of acceleration in relation to the ready-to-use universal version of the algorithm. So, the work considers a method for adapting the classical algorithm to specific needs, which are undirected tree-structure graphs.