On the difficulty of order constrained pattern matching with applications to feature matching based malware detection.

Adiesha Liyanage, Braeden Sopp, Binhai Zhu · 2025

Read On the difficulty of order constrained pattern matching with applications to feature matching based malware detection. by Adiesha Liyanage, Braeden Sopp, Binhai Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23176.txt.

Introduction

Adiesha Liyanage and co-authors wrote a 2025 computer science paper on the hard core of feature matching for malware hunting. Low level malware checks can be cast as a search for a pattern of colored blocks inside a program. Each block holds one key instruction, and a match must line up colors while the key signs form a reshuffle of each other.

The authors name three forms of the problem, from the loose general one to a strict form that demands a full pattern match. The strict form, they prove, is NP-complete, and so is the general one. Even ruling that no part of a pattern shows up is hard in a dual sense. Their upshot is blunt: feature matching tools face hard limits in theory.

Catalog record

CREATORAdiesha Liyanage, Braeden Sopp, Binhai Zhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-23176

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the difficulty of order constrained pattern matching with applications to feature matching based malware detection. Adiesha Liyanage, Braeden Sopp, Binhai Zhu Abstract Cybercrime, primarily in the form of malware, imposes substantial financial burden on its victims, with projections estimating its cost reaching $10 trillion by 2025. Malware detection in low-level programs using static analysis began as early as 2003, and feature extraction remains the dominant approach today. This research enabled subsequent signature-based and AI-based detection algorithms, all of which rely on feature matching in various ways. However, no theoretical analysis has been conducted on malware detection using algorithms based on features matching. In this paper, we examine malware detection through feature matching by formalizing the problem based on two observations from reality: (1) Most malware samples received by a single company belong to the same family or subfamily, exhibiting similarities in the low-level program structure, which consists of essentially disjoint blocks (each with a single entry and exit point); (2) Certain critical instruction sequences—such as opening a file followed by write operations, possibly preceded by API calls—are indicative of malware but not a guarantee. We formulate the problem of low-level malware detection using algorithms based on feature matching as Order-based Malware Detection with Critical Instructions (General-OMDCI): given a pattern in the form of a sequence M M of colored blocks, where each block contains a critical character (representing a unique sequence of critical instructions potentially associated with malware but without certainty), and a program A A , represented as a sequence of n n colored blocks with critical characters, the goal is to find two subsequences, M ′ M^{\prime} of M M and A ′ A^{\prime} of A A , with blocks matching in color and whose critical characters form a permutation of each other. When M M is a permutation in both colors and critical characters the problem is called OMDCI. If we additionally require M ′ = M M^{\prime}=M , then the problem is called OMDCI+; if in this case d = | M | d=|M| is used as a parameter, then the OMDCI+ problem is easily shown to be FPT. Our main (negative) results are on the cases when | M | |M| is arbitrary and are summarized as follows: 1. OMDCI+ is NP-complete, which implies OMDCI is also NP-complete. 2. For the special case of OMDCI, deciding if the optimal solution has length 0 0 (i.e., deciding if no part of M M appears in A A ) is co-NP-hard. As a result, the OMDCI problem does not admit an FPT algorithm unless P=co-NP. In summary, our results imply that using algorithms based on feature matching to identify malware or determine the absence of malware in a given low-level program are both hard. 1 Introduction Cybercrime, primarily carried out through malware attacks, occurs daily. Projections in 2020 indicated that its cost is expected to grow at an annual rate of 15%, reaching an estimated $10.5 trillion, up from $3 trillion in 2015 [ 16 ] . This cost exceeds the annual GDP of every country except the United States and China. Therefore, substantial research is necessary to prevent or at least mitigate malware spread. Notably, Christodorescu and Jha conducted the first research on extracting malware features using static analysis in low-level programs as early as 2003 [ 3 ] . Currently, feature extraction algorithms (and matching algorithms) are among the most widely used techniques for malware detection and analysis [ 1 , 2 , 8 , 10 , 12 , 21 ] . These methods involve static analysis, dynamic analysis, or a combination of both to extract features such as API calls and control flow graphs. Static analysis requires a deep understanding of malware structure, whereas dynamic analysis involves executing the program to traverse most, if not all, of its execution paths. On top of the features extracted, malware classification can be done using signature-based [ 5 , 17 , 19 , 20 ] and AI-driven algorithms, both methods are based on feature matching in different ways. Signature-based algorithms identify similar signature features in potential malware [ 14 ] , while AI-driven algorithms learn these features automatically from prior analysis using known features from training data. The latter certainly depends on the ability to automatically learn features from the corresponding AI packages (e.g., a neural network) [ 15 ] . In fact, data visualization has also become a viable solution for malware detection [ 11 ] . (As AI-based and visualization-based methods are not particularly relevant to this paper, we refer the reader to the following two papers for more details [ 11 , 15 ] .) Recently, Zhong et al. conducted a systematic study to classify malware into five families and 40 subfamilies [ 22 ] . The five families are: adware , worm , trojan , pua , and virus . The majority of subfamilies are under trojan which has 21 subfamilies. The basic idea of the research by Zhong et al. is to decompose a large program into blocks , each of which is a segment of the program with one entry point and one exit point, then applying machine learning methods to determine the similarity of blocks to an existing dataset. Although there has been extensive research on malware detection and classification from a practical side, less attention has been given to the algorithmic and computational complexity perspective. How hard is it to detect malware, even approximately? Can malware identified in one architecture B be used to detect malware in another architecture C? If so, what is the computational complexity of this process? As a starting point, we investigate some of these problems in this paper. Note that many malware are caused by system-based critical instructions, possibly preceded by API calls. Consider, for example, a potentially unwanted application (pua) . A pua is often produced by the remote injection of instructions into a local program, which then creates and opens a local file, writes unwanted contents into it, and ultimately forges and executes an unwanted application. In this process, the unique sequence of instructions \langle{\tt create},{\tt open},{\tt write}\rangle are critical instructions that collectively build a pua . Note that this sequence can be denoted as a single letter/character. However, the mere presence of these instructions does not necessarily imply the existence of pua . The general idea of our approach is based on these findings as well as the recent classification method by Zhong et al.; moreover, we follow an interesting finding by Ugarte-Pedrero et al., i.e., more than 70% of malware samples caught at a company belong to a known family or subfamily [ 18 ] . Consequently, identifying new malware based on its similarity to (a superset containing) other malware, as well as the sequence of critical instructions in them, is the key to this paper. We formulate a low-level program at an assembly language level as a sequence of blocks (each with one entry and exit point); moreover, the blocks have some similarity scores with existing programs written under the same architecture (i.e., with identical assembly instructions) — this can be done using existing AI packages [ 22 ] . Then, we give each block a unique color

Read the complete text