# CFG2VEC: Hierarchical Graph Neural Network for Cross-Architectural Software
Reverse Engineering††thanks: This material is based upon work supported by the
Defense Advanced Research Projects Agency (DARPA) and Naval Information
Warfare Center Pacific (NIWC Pacific) under Contract Number N66001-20-C-4024
The views, opinions, and/or findings expressed are those of the author(s) and
should not be interpreted as representing the official views or policies of
the Department of Defense or the U.S. Government. ††thanks: Distribution
Statement ”A” (Approved for Public Release, Distribution Unlimited).

Shih-Yuan Yu1, Yonatan Gizachew Achamyeleh1, Chonghan Wang1, Anton
Kocheturov2, Patrick Eisen2,  Mohammad Abdullah Al Faruque1 1Dept. of
Electrical Engineering and Computer Science, University of California, Irvine,
CA, USA {shihyuay, yachamye, chonghaw<EMAIL_ADDRESS>2Siemens Technology,
Princeton, NJ, USA, {anton.kocheturov<EMAIL_ADDRESS>
###### Abstract

Mission-critical embedded software is critical to our society’s infrastructure
but can be subject to new security vulnerabilities as technology advances.
When security issues arise, Reverse Engineers (REs) use Software Reverse
Engineering (SRE) tools to analyze vulnerable binaries. However, existing
tools have limited support, and REs undergo a time-consuming, costly, and
error-prone process that requires experience and expertise to understand the
behaviors of software and vulnerabilities. To improve these tools, we propose
cfg2vec, a Hierarchical Graph Neural Network (GNN) based approach. To
represent binary, we propose a novel Graph-of-Graph (GoG) representation,
combining the information of control-flow and function-call graphs. Our
cfg2vec learns how to represent each binary function compiled from various CPU
architectures, utilizing hierarchical GNN and the siamese network-based
supervised learning architecture. We evaluate cfg2vec’s capability of
predicting function names from stripped binaries. Our results show that
cfg2vec outperforms the state-of-the-art by 24.54% in predicting function
names and can even achieve 51.84% better given more training data.
Additionally, cfg2vec consistently outperforms the state-of-the-art for all
CPU architectures, while the baseline requires multiple training to achieve
similar performance. More importantly, our results demonstrate that our
cfg2vec could tackle binaries built from unseen CPU architectures, thus
indicating that our approach can generalize the learned knowledge. Lastly, we
demonstrate its practicability by implementing it as a Ghidra plugin used
during resolving DARPA Assured MicroPatching (AMP) challenges.

###### Index Terms:

Software Reverse Engineering; Binary Analysis; Cross-Architecture; Machine
Learning; Graph Neural Network;

##  I Introduction

In mission-critical systems, embedded software is vital in manipulating
physical processes and executing missions that could pose risks to human
operators. Recently, the Internet of Things (IoT) has created a market valued
at 19 trillion dollars and drastically grown the number of connected devices
to approximately 35 billion in 2025 [1, 2, 3]. However, while IoT brings
technological growth, it unintendedly exposes mission-critical systems to
novel vulnerabilities [4, 5, 6]. The reported number of IoT cyberattacks
increased by 300% in 2019 [7], while the discovered software vulnerabilities
rose from 1.6k to 100k [8]. The consequence can be detrimental, as indicated
in [9], the Heartbleed bug [10] can lead to a leakage of up to 64K memory,
threatening not only personal but also organizational information security.
Besides, Shellshock is a bash command-line interface shell bug, but it has
existed for 30 years and remains a threat to enterprises today [11, 12]. For
mission-critical systems, unexpected disruptions can incur millions of dollars
even if they only last for a few hours or minutes [13]. As a result, timely
analyzing these impacted software and patching vulnerabilities becomes
critical.

Figure 1: Legacy software life cycle.

However, mission-critical systems usually use software that can last for
decades due to the criticality of the missions. Over time, these systems
become legacy, and the number of newly-discovered threats can increase (as
illustrated in Figure 1). Typically, for legacy software, the original
development environment, maintenance support, or source code might no longer
exist. To address vulnerabilities, vendors offer patches in the form of source
code changes based on the current software version (e.g., ver 0.9). However,
the only available data in the legacy system is binary based on its source
code (e.g., ver 0.1). Such a version gap poses challenges in applying patches
to the legacy binaries, leaving the only solution for applying patches to
legacy software as direct binary analysis. Today, as Figure 2 shows, Reverse
Engineers (REs) have to leverage Software Reverse Engineering (SRE) tools such
as Ghidra [14], HexRays [15], and radare2 [16] to first disassemble and
decompile binaries into higher-level representations (e.g., C or C++).
Typically, these tools take the debugging information, strings, and the
symbol-table and binary to reconstruct function names and variable names,
allowing REs to rebuild a software’s structure and functionality without
access to source code [17]. For REs, these symbols encode the context of the
source code and provide invaluable information that could help them to
understand the program’s logic as they work to patch vulnerable binaries.
However, symbols are often excluded for optimizing the binary’s footprint in
mission-critical legacy systems where memory is limited. Because recovering
symbols from stripped binaries is not straightforward, most decompilers assign
meaningless symbol names to coding elements. As for understanding the software
semantics, REs have to leverage their experience and expertise to consume the
information and then interpret the semantics of each coding element.

Recent works tackle these challenges with Machine Learning (ML), aiming to
recover the program’s information from raw binaries. For example, [18], and
[19] associate code features to function names and model the relationships
between such code features and the corresponding source-level information
(variable names in [19], variable & function names in [18]). Meanwhile, [20]
and [21] use an encoder-decoder network structure to predict function names
from stripped binary functions based on instruction sequences and control
flows. However, none of them support cross-architectural debug information
reconstruction. On the other side, there exist works focusing on the cross-
platform in their ML models [22, 23, 24]. These works focus on modeling the
binary code similarity, extracting a real-valued vector from each control-flow
graph (CFG) with attributed features, and then computing the Structural
Similarity between the feature vectors of binary functions built from
different CPU architectures.

In this paper, as part of a multi-industry-academia joint initiative between
Siemens, the Johns Hopkins University Applied Physics Laboratory (JHU/APL),
BAE Systems (BAE), and UCI, we propose cfg2vec, which utilizes a hierarchical
Graph Neural Network (GNN) for reconstructing the name of each binary
function, aiming to develop the capacity for quick patching of legacy binaries
in mission-critical systems. Our Cfg2vec forms a Graph-of-Graph (GoG)
representation, combining CFG and FCG to model the relationship between binary
functions’ representation and their semantic names. Besides, cfg2vec can
tackle cross-architectural binaries thanks to the design of Siamese-based
network architecture, as shown in Figure 3. One crucial use case of cross-
architectural decompilation is patching, where the goal is to identify a known
vulnerability or a bug and apply a patch. However, there can be architecture
gaps when software with a bug can be compiled into many devices with diverse
hardware architectures. For example, it is challenging to patch a stripped
binary from an exotic embedded architecture compiled ten years ago that is
vulnerable to a known attack such as Heartbleed [10]. While the reference
patch is available in software, the reference architecture may not be readily
available or documented, or the vendor may no longer exist. Under such
circumstances, mapping code features across architectures is very helpful. It
would allow for identifying similarities in code between a stripped binary
that is vulnerable and its reference patch, even if the patch were built for a
different type of CPU architecture. For cfg2vec, our targeted contributions
are as follows:

  * •

We propose representing binary functions in Graph-of-Graph (GoG) and
demonstrate its usefulness in reconstructing function names from stripped
binaries.

  * •

We propose a novel methodology, cfg2vec that uses a hierarchical Graph Neural
Network (GNN) to model control-flow and function-calling relations in
binaries.

  * •

We propose using cross-architectural loss when training, allowing cfg2vec to
capture the architecture-agnostic representations of binaries.

  * •

We release cfg2vec in a GitHub repository:
https://github.com/AICPS/mindsight_cfg2vec.

  * •

We integrate our cfg2vec into an experimental Ghidra plugin, assisting the
realistic scenarios of patching DARPA Assured MicroPatching (AMP) challenge
binaries.

The paper is structured as follows: Section II discusses related works and
fundamentals to provide a better understanding of the paper. Section III
describes cfg2vec, including problem formulation, data preprocessing, and our
main pipeline introduction. Section IV shows our experimental results. Lastly,
we conclude the paper in Section V.

##  II Related Work

This section introduces software reverse engineering backgrounds, discusses
the related works using machine learning to improve reverse engineering, and
ultimately covers graph learning for binary analysis.

Figure 2: The RE flow to solve security issues.

###  II-A Software Reverse Engineering

Software Reverse Engineering (SRE) aims at understanding the behavior of a
program without having access to its source code, often being used in many
applications such as detecting malware [25, 26], discovering vulnerabilities,
and patching bugs in legacy software [27, 28]. One primary tool that Reverse
Engineers (REs) use to inspect programs is disassembler which translates a
binary into low-level assembly code. Examples of such tools include GNU
Binutils’ objdump [29], IDA [15], Binary Ninja [30], and Hopper [31]. However,
even with these tools, reasoning at the assembly level still requires
considerable cognitive effort from RE experts.

More recently, REs use decompilers such as Hex-Rays [32], or Ghidra [14] to
reverse the compiling process by further translating the output of
disassemblers into the code that ensembles high-level programming languages
such as C or C++ to reduce the burden of understanding assembly code. From
assembly instructions, these decompilers can use program analysis and
heuristics to reconstruct variables, types, functions, and control flow
structure of a binary. However, the decompilation is incomplete even if these
decompilers generate a higher-level output for better code understanding. The
reason is that the compilation process discards the source-level information
and lowers its abstraction level in exchange for a smaller footprint size,
faster execution time, or even security considerations. The source-level
information such as comments, variable names, function names, and idiomatic
structure can be essential for understanding a program but is typically
unavailable in the output of these decompilers.

As Figure 2 demonstrated, REs use disassemblers or decompilers to generate
high-level source code. Besides, [33] indicates REs will take notes and grant
a name to those critical functions related to the vulnerabilities. This will
create an annotated source code based on the high-level machine-generated
source code. While annotating the source code, REs also analyze the
significant part related to the vulnerability and ignore those general
instructions or unrelated codes. At the same time, understanding the logic
flow among functions is another major task they must focus on resolving their
tasks. After classification, annotation, and understanding, REs experiment
with several viable remedies to find the correct patch to fix the
vulnerability.

###  II-B Machine Learning for Reverse Engineering

Software binary analysis is a straightforward first step to enhance security
as developers usually deploy software in binaries [34]. Usually, experts
conduct the patching process or vulnerability analysis by understanding the
compilation source, function signatures, and variable information. However,
after the compilation, such information is usually stripped or confuscated
deliberately (e.g., obfuscation). Software binary analysis becomes more
challenging in this case as developers have to recover the source-level
information based on their experience and expertise. The early recovery work
for binaries focuses on manual completion but suffers from low efficiency,
high cost, and the error-prone nature of reverse engineering.

As Machine Learning (ML) has significantly advanced in its reasoning
capability, applying ML and reconstructing higher-level source code
information as an alternative to manual-based approaches has attracted
considerable research attention. For example, [35] was the first approach that
used neural network-based and graph-based models, predicting the function
types to assist the reverse engineer in understanding the binary. [36] also
predicted function names with neural networks, aggregating the related
features of sections of binary vectors. Then, it analyzes the connections
between each function in the source code (e.g., Java) and their corresponding
function names for function name prediction. [18], on the other hand, did not
use a neural network. It combined a decision-tree-based classification
algorithm and a structured prediction with a probabilistic graphical model,
then matched the function name by analyzing symbol names, types, and
locations. However, [18] can only predict from a predetermined closed set,
incapable of generalizing to new names.

As the languages for naming functions are similar to natural language, recent
research works start leaning toward the use of Natural Language Processing
(NLP)[37, 20, 21]. Precisely, these models predict semantic tokens based on
the function names in the library, comprising the function name during
inference. The underlying premise is that each token corresponds in some way
to the attributes and functionality of the function. [20] uses Control-Flow
Graph (CFG) to predict function names. It combined static analysis with LSTM
and transformer neural model to realize the name of functions. However, the
dataset that consisted of unbalanced data and insufficient features was
limited and hindered utter performance. [37] was designed to solve the
limitation of the dataset. It provided UbuntuDataset that contained more than
9 million functions in 22K software. [21] demonstrated the framework’s
effectiveness by building a large dataset. It considers the fine-grained
sequence and structure information of assembly code when modeling and
realizing function name prediction. Meanwhile, [21] reduced the diversity of
data (instructions or words) while keeping the basic semantics unchanged,
similar to word stemming and semantics in NLP. However, these works have low
precision scores for prediction tasks, exampled by [21], only achieving around
41% in correctly predicting the function name subtokens. Moreover, the metrics
for the inference of unknown functions are substantially lower [21], making it
difficult for REs to find it helpful in practice.

Although many existing works can reconstruct source-level information, none of
them supports reconstructing cross-platform debug information. Cross-
compilation is becoming more popular in the development of software. Hardware
manufacturers, for instance, often reuse the same firmware code base across
several devices running on various architectures [38]. A tool that performs
cross-architecture function name prediction/matching would be beneficial if we
have a stripped binary compiled for one architecture and a binary of a
comparable program compiled for another architecture with debug symbols. We
may use the binary with the debug symbols to predict the names of functions in
the stripped binary, which significantly aids debugging. A tool that could
capture the architecture-agnostic characteristics of binaries would also help
in malware detection as the source code of malware can be compiled in
different architectures [38, 39]. Comparing two binaries of different
architectures becomes more complicated because they will have different
instruction sets, calling conventions, register sets, etc. Furthermore,
assembly instructions from different architectures cannot often be compared
directly due to the slightly different behavior of different architectures
[40]. Cross-architecture function name prediction will assist in finding a
malicious function in a program compiled for different architectures by
learning its features from a binary compiled for just one architecture. The
tools mentioned above are not architecture-agnostic; thus, we cannot utilize
them for such applications. To address the flaws mentioned above, aid in
creating more efficient decompilers, and make reverse engineering more
accessible, we propose cfg2vec. Incorporating the cross-architectural siamese
network architecture, our cfg2vec can learn to extract robust features that
encompass platform-independent features, enhancing the state-of-the-art by
achieving function name reconstruction across cross-architectural binaries.

###  II-C Graph Learning for Binary Analysis

Figure 3: An example of a Graph-of-Graph (GoG) of a binary compiled from a
package Freecell with amd64 CPU architecture.

Graph learning has become a practical approach across fields [41, 42, 43, 44].
Although conventional ML can effectively capture the features hidden in
Euclidean data, such as images, text, or videos, our work focuses more on the
application where the core data is graph-structured. Graphs can be irregular,
and a graph may contain a variable size of unordered nodes; moreover, nodes
can have a varying number of neighboring nodes, making deep learning
mathematical operations (e.g., 2D Convolution) challenging to apply. The
operations in conventional ML methods can only be applied by projecting non-
Euclidean data into low-dimensional embedding space. In graph learning, Graph
Embeddings (GE) can transform a graph into a vector (embedding of a graph) or
a set of vectors (embedding of nodes or edges) while preserving the relevant
and structural information about the graph [41]. Graph Neural Network (GNN) is
a model aiming at addressing graph-related tasks in an end-to-end manner,
where the main idea is to generate a node’s representation by aggregating its
representation and the representations of its neighbors [42]. GNN stacks
multiple graph convolution layers, graph pooling layers, and a graph readout
to generate a low-dimensional graph embedding from high-dimensional graph-
structured data.

In software binary analysis, many approaches use Control-Flow Graphs (CFGs) as
the primary representations. For example, Genius forms an Attributed Control-
Flow Graph (ACFG) representation for each binary function by extracting the
raw attributes from each Basic Block (BB), a straight-line code sequence with
no branching in or out except at the entry and exit, in an ACFG [22]. Genius
measures the similarity of a pair of ACFGs through a bipartite graph matching
algorithm, and the ACFGs are then clustered based on similarity. Genius
leverages a codebook for retrieving the embedding of an ACFG based on
similarity. Another approach, Gemini, proposes a deep neural network-based
model along with a Siamese architecture for modeling binary similarities with
greater efficiency and accuracy than other state-of-the-art models of the time
[23]. Gemini takes in a pair of ACFGs extracted from raw binary functions
generated from known vulnerability in code and then embeds them with a shared
Structure2vec model in their network architecture. Once embedded, Gemini
trains its model with a loss function that calculates the cosine similarities
between two embedded representations. Gemini outperforms models like Genius or
other approaches such as bipartite graph matching. In literature, there exist
other works that consider the Function Call Graph (FCG) as their primary data
structures in binary analysis for malware detection [45]. Our cfg2vec extracts
relevant platform-independent features by combining the usage of CFG and FCG,
resulting in a Graph-of-Graph (GoG) representation for cross-architectural
high-level information reconstruction tasks (e.g., function name).

##  III CFG2VEC Architecture

This section begins with problem formulation. Next, as Figure 4 shows, we
depict how our cfg2vec extracts the Graph-of-Graph (GoG) representation from
each software binary. Lastly, we describe the network architecture in cfg2vec.

###  III-A Problem Formulation

In our work, given a binary code, denoted as $p$, compiled from different CPU
architectures, we extract a graph-of-graph (GoG) representation,
$\mathpzc{G}=(\mathpzc{V},\mathpzc{A})$ where $\mathpzc{V}$ is the set of
nodes and $\mathpzc{A}$ is the adjacency matrix (As Figure 3 shows). The nodes
in $\mathpzc{V}$ represent functions and the edges in $\mathpzc{A}$ indicate
their cross-referencing relationships. That says, each of the node
$f_{i}\in\mathpzc{V}$ is a CFG, and we denote it as $f_{i}=(B,A,\phi)$ where
the nodes in $B$ represent the basic blocks and the edges in $A$ denote their
dependency relationships. $\phi$ is a mapping function that maps each basic
block in the assembly form to its corresponding extracted attributes
$\phi(v_{i})=C^{k}$ where C is a numeric value, and k is the number of
attributes for the basic block (BB). Whereas the CFG structure is meant to
provide more information at the lower BB level, the GoG structure is intended
for recovering information at the overarching function level between the CFGs.
Figure 3 is an example of a partial GoG structure with a closer inspection of
one of its CFG nodes and another of a single CFG BB node, showing the set of
features corresponding to that BB node. The goal is to design an efficient and
effective graph embedding technique that can be used for reconstructing the
function names for each function $f_{i}\in\mathpzc{V}$.

###  III-B Ghidra Data ToolKit for Graph Extraction

To extract the structured representation required for cfg2vec we leverage the
state-of-the-art decompiler Ghidra [14] and the Ghidra Headless
Analyzer111Documentation of Ghidra Headless Analyzer:
https://ghidra.re/ghidra_docs/analyzeHeadlessREADME.html. The headless
analyzer is a command-line version of Ghidra allowing users to perform many
tasks (such as analyzing a binary file) supported by Ghidra via a command-line
interface. For extracting GoG from a binary, we developed our Ghidra Data
Toolkit (GDT); GDT is a set of Java-based metadata extraction scripts used for
instrumenting Ghidra Headless Analyzer. First, GDT programmatically analyzes
the given executable file and stores the extracted information in the internal
Ghidra database. Ghidra provides a set of APIs to access the database and
retrieve the information about the analyzed binary. GDT uses these APIs to
export information such as Ghirda’s PCode and call graph for each function.
Specifically, the FunctionManager API allows us to manipulate the information
of each decompiled function in the binary and acquire the cross-calling
dependencies between functions. For each function, we utilized another Ghidra
API DecompInterface222Documentation of Ghidra API DecompInterface:
https://ghidra.re/ghidra_docs/api/ghidra/app/decompiler/DecompInterface.html
to extract 12 attributes associated with each basic block in a function. These
attributes precisely correspond to the total number of instructions, including
arithmetic, logic, transfer, call, data transfer, SSA, compare, and pointer
instructions, as well as other instructions not falling within those
categories and the total number of constants and strings within that BB.
Lastly, by integrating all of the information, we form a GoG representation
$\mathpzc{G}$ for each binary $p$. We repeat this process until all binaries
are converted to the GoG structure. We feed the resulting GoG representations
to our model in batches, with the batch size denoted as B.

###  III-C Hierarchical Graph Neural Network

Figure 4: The architecture of cfg2vec with a supervised hierarchical graph
neural network approach.

Once $\mathpzc{G}$ is extracted from the GDT, we then feed it to our
hierarchical network architecture (inspired from [46]) that contains both CFG
Graph Embedding layer and GoG Graph Embedding Layer as Figure 4 shows. For
each GoG structure, we denote it as $\mathpzc{G}=(\mathpzc{V},\mathpzc{A})$
where $\mathpzc{V}$ is a set of functions associated with $\mathpzc{G}$ and
$\mathpzc{A}$ indicates the calling relationships between the functions in
$\mathpzc{V}$. Each function in $\mathpzc{V}$ is in the form of CFG
$f_{i}=(B,A,\phi)$ where each node $b\in B$ is a BB represented in a fixed-
length attributed vector $b\in R^{d}$, and $d$ is the dimension that we have
mentioned earlier. $A$ encodes the pair-wise control-flow dependency
relationships between these BBs.

####  III-C1 CFG Graph Embedding Layer

Our network architecture first feeds all functions in a batch of GoGs to the
CFG Graph Embedding Layer consisting of multiple graph convolutional layers
and a graph readout operations. The input to this layer is a function
$f_{i}=(B,A,\phi)$ and the output is the fixed-dimensional vector representing
a function. For each BB $b_{k}$ we let $b_{k}^{0}=b_{k}$, and we update
$b_{k}^{t}$ to $b_{k}^{t+1}$ with the graph convolution operation shown as
follows:

$b_{k}^{t+1}=f_{G}(Wb_{k}^{t}+\sum_{b_{m}\in A_{k}}Mb_{m}^{t})$

where $f_{G}$ is a non-linear activation function such as ReLU, $A_{k}$ is the
list of adjacent BBs for $b_{k}$, and $W\in R^{d\times d}$ and $M\in
R^{d\times d}$ are the weights to be learned during the training. We run $T$
iterations of such a convolution, which can be a tunable hyperparameter in our
model. During the updates, each BB gradually aggregates the global information
of the control-flow dependency relations into its representation, utilizing
the representation of its neighbor. We obtain the final representation for
each BB as $b_{k}^{T}$. To acquire the representation for the function
$f_{i}$, we apply a graph readout operation such as sum-readout, described as
follows,

$g^{(T)}=\sum_{b_{k}\in B}b_{k}^{T}$ (1)

We assign the value of $g^{(T)}$ (a.k.a. CFG embedding) to $f_{i}$. The graph
readout operation can be replaced with mean-readout or max-readout.

####  III-C2 GoG Graph Embedding Layer

Once all the functions have been converted to fixed-length graph embeddings,
we then feed $\mathpzc{G}$ to the second layer of cfg2vec, the GoG Embedding
Layer. Here, for each function $f_{i}$ we apply another $L$ iterations of
graph convolution with $\mathpzc{F}$ and $\mathpzc{C}$. The updates can be
illustrated as follows,

$f_{k}^{(l+1)}=f_{GoG}(Uf_{k}^{l}+\sum_{f_{m}\in C_{k}}Vf_{m}^{(l)})$ (2)

where $f_{GoG}$ is a non-linear activation function and $C_{k}$ is the list of
adjacent functions (calling) for the function $f_{k}$ and $U\in R^{d\times d}$
and $V\in R^{d\times d}$ are the weights to be learned during the training.
Lastly, we take the $f_{k}^{(L)}$ as the representation that considers both
CFG and GoG graph structures. We use these updated representations to perform
cross-architecture function similarity learning.

####  III-C3 Siamese-based Cross-Architectural Function Similarity

Given a batch of GoGs $B=\\{GoG_{1},GoG_{2},...,GoG_{B}\\}$, we apply the
hierarchical graph neural network to acquire the set of updated function
embeddings, denoted as $B_{F}=\\{f_{1}^{(T)},f_{2}^{(T)},...,f_{K}^{(T)}\\}$.
We calculate the function similarity for each function pair with cosine
similarity, denoted as $\hat{y}\in[-1,1]$. The loss function $J$ between
$\hat{Y}$ and a ground-truth label $y$, which indicates whether a pair of
functions have the same function or not, is calculated as follows,

$J(\hat{y},y)=\left\\{\begin{array}[]{ll}1-y,&\text{if y=1,}\\\
MAX(0,\hat{y}-m),&\text{if y=-1,}\end{array}\right.$ (3)

the final loss $L$ is then calculated as follows,

$L=H(Y,\hat{Y})=\sum_{i}(J(\hat{y_{i}},y_{i})),$ (4)

where $Y$ stands for ground-truth labels (either similarity or dissimilarity),
and $\hat{Y}$ represents the corresponding predictions. More specifically, we
denote a pair of functions as similar if they are the same but compiled with
different CPU architectures. The $m$ is a constant to prevent the learned
embeddings from becoming distorted (by default, $0.5$). To maintain the
balance between positive and negative training samples, we developed a custom
batching algorithm. The function leverages the knowledge gained by adding a
binary of some package to a given batch to find and add a binary for the same
package, built for a different architecture, to the provided batch as a
positive sample. It will also include a binary from another package as a
negative sample. This will give any batch a balanced proportion of positive
and negative samples. Finally, we use the loss $L$ to update all the
associated weights in our neural networks with an Adam optimizer. Once
trained, we then use the model to perform function name reconstruction tasks.

##  IV Experimental Results

In this section, we evaluate cfg2vec’s capability in predicting function
names. We first describe the dataset preparation and the training setup
processes. Then, we present the comparison of cfg2vec against baseline in
predicting function names. Although many baseline candidates tackle the same
problem [18, 37, 20, 21], some require purchasing a paid version of IDA Pro to
preprocess datasets, and some even do not open source their implementations.
Therefore, [18] was the only feasible choice, as running other models using
our datasets was almost impossible. Next, we also show the result of the
ablation study over cfg2vec. Besides, we exhibit that our cfg2vec can perform
architecture-agnostic prediction better than the baseline. Lastly, we
illustrate the real-world use case where our cfg2vec is integrated as a Ghidra
plugin application for assisting in resolving challenging reverse engineering
tasks. We conducted all experiments on a server equipped with Intel Core
i7-7820X CPU @3.60GHz with 16GB RAM and two NVIDIA GeForce GTX Titan Xp GPUs.

###  IV-A Dataset Preparation

Our evaluating data source is the ALLSTAR (Assembled Labeled Library for
Static Analysis Research) dataset, hosted by Applied Physics Laboratory (APL)
[47]. It has over 30,000 Debian Jessie packages pre-built from i386, amd64,
ARM, MIPS, PPC, and s390x CPU architectures for software reverse engineering
research. The authors used a modified Dockcross script in docker to build each
package for each supported architecture. Then, they saved each resulting ELF
with its symbols, the corresponding source code, header files, intermediate
files (.o, .class, .gkd, .gimple), system headers, and system libraries
altogether.

To form our datasets, we selected the packages that have ELF binaries built
for the amd64, armel, i386, and mipsel CPU architectures. i386 and amd64 are
widely used by general computers, especially in the Intel and AMD products,
respectively. MIPS and ARM are crucial in embedded systems, smartphones, and
other portable electronic devices [48]. In practice, we excluded the packages
with only one CPU architecture in the ALLSTAR dataset. Additionally, due to
our limited local computing resources, we eliminated packages that were too
large to handle. We checked each selected binary on whether the ground-truth
symbol information exists using the Ghidra decompiler and Linux file command
and removed the ones that do not have them. Lastly, we assembled our primary
dataset, called the AS-4cpu-30k-bin dataset, that consists of 27572 pre-built
binaries from 1117 packages and 4 CPU architectures, as illustrated in Table
I.

Our preliminary experiment revealed that the evaluation had a data leakage
issue when splitting the dataset randomly. Therefore, we performed a non-
random variant train-test split with a 4-to-1 ratio on the AS-4cpu-30k-bin
dataset, selecting roughly 80% of the binaries for the training dataset and
leaving the rest for the testing dataset. We referenced [23] for their
splitting methods, aiming to ensure that the binaries that belong to the same
packages stay in the same set, either the training or testing sets. Such a
variant splitting method allows us to evaluate cfg2vec truly.

Next, we converted binaries in the AS-4cpu-30k-bin dataset into their Graph-
of-Graph (GoG) representations leveraging the GDT mentioned previously in
Section III-B. Notably, we processed a batch of binaries related to one
package at one time as developers might define user functions in different
modules of the same package while putting prototype declarations in that
package’s main module. For this case, Ghidra indeed recognizes two function
instances while one only contains the function declaration and another has its
actual function content. As these two instances correspond to the same
function name and one contains only dummy instructions, they can thus create
noise in our datasets, thus affecting our model’s learning. To cope with this,
our GDT also searches from other binaries of the same package for the function
bodies. If found, our GDT associates that user function with the function
graph node with the actual content data. Besides user functions, library
function calls may exist, and searching their function bodies in the same
package would fail for dynamically loaded binaries. Under such circumstances,
Ghidra would recognize these functions as ThunkFunctions333ThunkFunction
Manual:
https://ghidra.re/ghidra_docs/api/ghidra/program/model/listing/ThunkFunction.html
which only contain one dummy instruction. As a workaround, we removed these
ThunkFunctions from our data as they might mislead the model’s learning.
Applying this workaround indicates that our model works in predicting function
names for the user and statically linked functions.

TABLE I: The statistics of datasets used in our experiments. Dataset / # | pkg/bin | func node/edge1 | bb node/edge2
---|---|---|---
AS-4cpu-30k-bin | 1117/27,572 | 51.17/97.14 | 14.12/19.98
AS-3cpu-9k-bin | 633/9,000 | 44.01/79.06 | 12.24/17.07
AS-i386-3k-bin | 633/3,000 | 45.31/87.70 | 11.45/15.97
AS-amd64-3k-bin | 633/3,000 | 42.28/74.07 | 12.28/17.18
AS-armel-3k-bin | 633/3,000 | 44.45/75.41 | 13.00/18.07
1 # of average functions and edges in each binary
2 # of average bb blocks and edges from each function
TABLE II: The performance evaluation of cfg2vec for function name prediction against [18]. Model | Training dataset | Testing dataset | P@11 | P@21 | P@31 | P@41 | P@51
---|---|---|---|---|---|---|---
cfg2vec | AS-4cpu-30k-bin | AS-noMipsel-300-bin | 97.05% | 99.47% | 99.47% | 99.47% | 99.47%
cfg2vec | AS-4cpu-20k-bin | AS-noMipsel-300-bin | 74.22% | 75.76% | 75.78% | 75.78% | 78.78%
|  | AS-amd-100-bin | 69.18% | 69.98% | 69.98% | 69.98% | 69.98%
cfg2vec | AS-3cpu-9k-bin | AS-i386-100-bin | 69.41% | 70.39% | 70.39% | 70.39% | 70.39%
|  | AS-armel-100-bin | 70.66% | 71.04% | 71.11% | 71.11% | 71.11%
|  | AS-noMipsel-300-bin | 69.75% | 70.47% | 70.50% | 70.50% | 70.50%
[18]-amd642 | AS-amd64-3k-bin | AS-amd-100-bin | 29.32% | - | - | - | -
[18]-i3862 | AS-i386-3k-bin | AS-i386-100-bin | 52.64% | - | - | - | -
[18]-armel2 | AS-armel-3k-bin | AS-armel-100-bin | 53.65% | - | - | - | -
1 P@k measures if the actual function name is in the top k of the predicted
function names.
2 These models only provide the top 1 function name prediction; hence they
only have P@1 value.

We experimented [18] with our datasets, referencing to their
implementation444Debin’s [18] repository: https://github.com/eth-sri/debin. As
[18] used a dataset with 3,000 binaries for experiments, we followed
accordingly, preparing datasets with smaller but similar sizes. We achieved
this by downsampling from our primary AS-4cpu-30k-bin dataset, creating the
AS-3cpu-9k-bin dataset which has 9,000 binaries for i386, amd64, and armel CPU
architectures. Furthermore, as [18] supports only one CPU architecture at a
time, we then separated the AS-3cpu-9k-bin dataset into different CPU
architectures, generating three training datasets for testing [18]:
AS-i386-3k-bin, AS-amd64-3k-bin, and AS-armel-3k-bin. For training, we
utilized the strip Linux command, converting our original data into three: the
original binaries (debug), stripped binaries with debug information
(stripped), and stripped binaries without debug information
(stripped_wo_symtab) to follow [18]’s required data format. For evaluation, we
sampled 100 binaries from our primary dataset for each CPU architecture,
labeled AS-amd-100-bin, AS-i386-100-bin, AS-armel-100-bin, and AS-
mipsel-100-bin. We also have another evaluation dataset called AS-
noMipsel-300-bin, which contains roughly 300 binaries produced for the amd64,
i386, and armel platforms. Table I summarizes the data statistics for all
these datasets, including the numbers of packages and binaries, the average
number of function nodes, edges, and BB nodes. The following sections will
detail how we utilized these datasets during our experiments.

###  IV-B Evaluation: Function Name Prediction

Table II demonstrates the results of cfg2vec in predicting function names. For
the baseline, we followed [18]’s best setting where the feature dimension of
register or stack offset are both 100 to train with our prepared datasets. For
cfg2vec, we used three GCN layers and one GAT convolution layer in both graph
embedding layers. For evaluation, we calculate the p@k (e.g., precision at k)
metric, which refers to an average hit ratio over the top-k list of predicted
function names. Specifically, we feed each binary represented in GoG into our
trained model, converting each function $f\in F$ and acquiring its function
embedding $h_{f}$. Then, we calculate pair-wise cosine similarities between
$h_{f}$ and all the other function embeddings, forming a top-k list by
selecting k names in which their embeddings are top-kth similar to $h_{f}$. If
the ground-truth function name is among the top-k list of function name
predictions, we regard that as a hit; otherwise, it is a miss. During
experiments, we set the top-k value to be 5, so our model can recommend the
best five possible names for each function in a binary.

As shown in Table II, cfg2vec, trained with the AS-3cpu-9k-bin dataset, can
achieve a 69.75% prediction accuracy (e.g., p@1) in inferring function names.
For [18], we had to train their models for each CPU architecture separately as
it cannot train in a cross-architectural manner. Even so, for amd64 binaries,
[18] only achieves 29.32% precision, while for i386 and armel, it performs
52.64% and 53.65%, respectively. This result indicates that in any case, our
cfg2vec outperforms [18]. Besides, while [18] only yields one prediction, our
cfg2vec suggests five choices, making it flexible for our users (e.g., REs) to
select what they believe best fits the function among the best k predicted
names. The p@2 to p@5 in Table II demonstrate that our cfg2vec can provide
enough hints of function names for users. For example, p@5 of cfg2vec trained
with our AS-3cpu-9k-bin dataset can achieve 70.50% precision across all the
CPU architecture binaries. We also experimented our cfg2vec with larger
datasets. From Table II, we can observe that cfg2vec can have 5.04%
performance gain in correctly predicting function names (e.g., p@1). Moreover,
the gain increases to 28% when training cfg2vec with the AS-4cpu-30k-bin
dataset. We believe training on a larger dataset implies training with a more
diversified set of binaries. This allows our model to acquire more knowledge,
thus being capable of extracting more robust features for binary functions. In
summary, this result indicates that compared to the baseline, our model can
effectively provide contextually relevant names for functions in the
decompiled code to our users.

TABLE III: The comparison between cfg2vec and its ablated variations. Arch | [18] | GCN-GAT | 2GCN | 2GCN-GAT | cfg2vec
---|---|---|---|---|---
amd64 | 29.32%1 | 61.59% | 69.49% | 69.56% | 70.66%
armel | 52.64%2 | 66.40% | 68.59% | 68.92% | 69.19%
mipsel | 53.65%3 | 66.47% | 68.17% | 68.56% | 69.41%
Overall | 45.20% | 64.82% | 68.75% | 69.01% | 69.75%
1 Evaluation results for [18]-amd64 model.
2 Evaluation results for [18]-i386 model.
3 Evaluation results for[18]-armel model.

We also experimented with various ablated network setups to study how each
component of cfg2vec contributes to performance. First, we simplified our
cfg2vec by stripping one GCN layer from the original experimental setup. As
shown in Table III, we called this setup 2GCN-GAT which slightly decreased the
performance by 0.75%. Then, from 2GCN-GAT setup, we further removed the GAT
layer, calling it 2GCN. We again observed a marginal performance decrease
($<$1%). Next, we eliminated another GCN layer from 2GCN-GAT, constructing the
GCN-GAT setup. For GCN-GAT, we saw a drastic drop (4.2%) which highlights that
the number of GCN layers can be an essential factor in the performance.
Specifically, we found that going from 1 to 2 GCN layers improves prediction
accuracy by more than 4%. However, we do not observe a significant performance
gain when increasing the number of GCN layers to more than three. Therefore,
we retained the original cfg2vec model with its three GCN layers. All in all,
as shown in Table III, all these ablated models, still outperform [18], which
we attributed to the GoG representation we made for each binary in the
dataset.

###  IV-C Evaluation: Architectural-agnostic Prediction

Table IV demonstrates our cfg2vec’s capability in terms of cross-architecture
support. As [18] supports training one CPU architecture at a time, we had to
train it multiple times during experiments. Specifically, we trained [18] on
three datasets: AS-amd64-3k-bin, AS-i386-3k-bin, and AS-armel-3k-bin, calling
resulting trained models, [18]-amd64, [18]-i386, and [18]-armel, respectively.
For these baseline models, we observe that they perform well when tested with
the binaries built on the same CPU architecture but poorly with the ones built
on different CPU architectures. For instance, [18]-amd64 achieves 29.3%
accuracy for amd64 binaries, but performs worse for i386 and armel binaries
(13.8% and 7.1%). Similarly, [18]-i386 achieves 52.6% accuracy for i386
binaries, but performs worse for amd64 and armel binaries (6.2% and 1.1%).
Lastly, [18]-armel achieves 53.6% accuracy for armel binaries, but performs
worse for amd64 and i386 binaries (11.8% and 8.9%). We used the top-1
prediction generated from cfg2vec (a.k.a., p@1) as the comparing metric as
[18] produces only one prediction per each function. From the results, we
observe that cfg2vec outperforms [18] across all three tested CPU
architectures. The fact that cfg2vec performs consistently well across all CPU
architectures indicates that our cfg2vec supports cross-architecture
prediction.

To evaluate the capability of generalizing the learned knowledge, we tested
all models with the AS-mipsel-100-bin dataset, which has binaries built from
another famous CPU architecture, mipsel, that our cfg2vec does not train
before. For [18], it has lower performance when testing on binaries built from
the CPU architectures that it did not train before, exampled by the highest
accuracy of [18] to be 13.84% when trained on amd64 binaries and evaluated on
i386 binaries. In our work, as Table IV shows, our cfg2vec achieves 36.69%
accuracy when trained with amd64, i386, and armel binaries but tested on
mipsel binaries. For [18], it does not even support analyzing mipsel binaries.
In short, these results demonstrate that our cfg2vec outperforms our baseline
in the function name prediction task on cross-architectural binaries and
generalizes better to the binaries built from unseen CPU architectures. To
further investigate cfg2vec’s cross-architecture performance, we trained it on
three datasets, each consisting of binaries built for two different
architectures. We then gave the resulting trained models names that indicated
the architectures from which the binaries were derived: cfg2vec-armel-i386,
cfg2vec-amd64-i386, and cfg2vec-armel-amd64. These results show that our model
performs well in the function name prediction job across all of these
scenarios, including when tested on binaries compiled for unknown CPU
architectures.

TABLE IV: The cross-architectural comparison between cfg2vec and [18] Model |  Testing dataset | P@1
---|---|---
|  AS-amd-100-bin | 69.18%
cfg2vec-3-Arch |  AS-i386-100-bin | 70.66%
|  AS-armel-100-bin | 69.41%
|  AS-mipsel-100-bin∗ | 36.69%
|  AS-amd-100-bin | 68.53%
cfg2vec-amd64-armel |  AS-i386-100-bin∗ | 39.23%
|  AS-armel-100-bin | 69.11%
|  AS-mipsel-100-bin∗ | 32.21%
|  AS-amd-100-bin | 68.59%
cfg2vec-amd64-i386 |  AS-i386-100-bin | 69.09%
|  AS-armel-100-bin∗ | 34.20%
|  AS-mipsel-100-bin∗ | 38.26%
|  AS-amd-100-bin∗ | 42.96%
cfg2vec-armel-i386 |  AS-i386-100-bin | 67.45%
|  AS-armel-100-bin | 63.86%
|  AS-mipsel-100-bin∗ | 36.61%
|  AS-amd-100-bin | 29.32%
[18]-amd64 |  AS-i386-100-bin∗ | 13.84%
|  AS-armel-100-bin∗ | 7.08%
|  AS-mipsel-100-bin∗ | -
|  AS-amd-100-bin∗ | 6.23%
[18]-i386 |  AS-i386-100-bin | 52.64%
|  AS-armel-100-bin∗ | 1.05%
|  AS-mipsel-100-bin∗ | -
|  AS-amd-100-bin∗ | 11.82%
[18]-armel |  AS-i386-100-bin∗ | 8.86%
|  AS-armel-100-bin | 53.65%
|  AS-mipsel-100-bin∗ | -
∗ indicates that dataset was not used during the training.

###  IV-D The Practical Usage of CFG2VEC

In this section, we demonstrate how cfg2vec assists REs in dealing with
Defense Advanced Research Projects Agency (DARPA) Assured MicroPatching (AMP)
challenges binaries. The AMP program aims at enabling fast patching of legacy
mission-critical system binaries, enhancing decompilation and guiding it
toward a particular goal of a Reverse Engineer (RE) by integrating the
existing source code samples, the original build process information, and
historical software artifacts.

####  IV-D1 The MINDSIGHT project

our multi-industry-academia initiative between Siemens, JHU/APL, BAE, and UCI
jointly developed a project, Making Intelligible Decompiled Source by Imposing
Homomorphic Transforms (MINDSIGHT). Our team focused on building an automated
toolchain integrated with Ghidra, aiming to enable the decompilation process
with (1) a less granular identification of modular units, (2) an accurate
reconstruction of symbol names, (3) the lifting of binaries to stylized C
code, (4) a principled and scalable approach to reason about code similarity,
and (5) the benchmarking of new decompilation techniques using state-of-the-
art embedded software binary datasets. To date, our team has developed an
open-source tool, CodeCut555 CodeCut’s repository:
https://github.com/DARPAMINDSIGHT/CodeCut, to improve the accuracy and
completeness of Ghidra’s module identification, providing an automated script-
based decompilation analysis toolchain to ease the RE’s expert interpretation.
Besides, we also developed a Homomorphic Transform Language (HTL) to describe
transformations on Abstract Syntax Tree (AST) languages and the rules of their
composition. Our tool, integrated with ghidra, allows developers to transform
the decompiled code syntactically while keeping it semantically equivalent.
The key idea is to use this HTL to morph a Ghidra AST into a GCC AST to lift
the decompiled binary to a high-level C representation. This process can make
it easier for REs to comprehend the binary code. cfg2vec is another tool
developed in the MINDSIGHT project, enabling the reconstruction of function
names, saving the manual guesswork from REs.

Figure 5: The plugin screenshot integrated into Ghidra.

####  IV-D2 The cfg2vec plugin

In MINDSIGHT project, we incorporated cfg2vec into Ghidra decompiler as a
plugin application. Our cfg2vec plugin assists REs in comprehending the
binaries by providing a list of potential function names for each function
without its name. Technically, like all Ghidra plugins, our cfg2vec plugin
bases on Java with its core inference modules implemented as a REST API in
Python 3.8. Once the metadata of a stripped binary is extracted from Ghidra
decompiler, it is then sent to the cfg2vec end-point, which calculates and
returns the inferred mappings for all the functions. Figure 5 demonstrates the
user interface of our cfg2vec plugin. In this scenario, the user must provide
the vulnerable and the reference binary with extra debug information, such as
function names. The “Match Functions” button triggers cfg2vec functionality
and displays the function mapping results in three tables:

  * •

Matched Table: displays the mapping of similar functions.

  * •

Mismatched Table: displays the mapping of dissimilar functions and, therefore,
candidates for patching.

  * •

Orphan Table: displays the mapping of functions with a low confidence score.

The groupings reduce REs’ workload. Rather than inspecting all functions, they
can focus on patching candidate functions (mismatched functions) and the
orphans. The “Explore Functions” button invokes Ghidra’s function explorer,
where the two functions can be compared side-by-side, as shown in Figure 5.
This utility allows the user to switch between C and assembly language, thus
assisting in confirming or modifying the mappings from the three tables.
Regarding cfg2vec’s function prediction, the “Rename Function” button takes
the selected row from the tables and imposes the name from the patched binary
in the vulnerable binary. When the “Match Functions” button fires, we invoke
the FCG and CFG generators for the two programs (vulnerable and patched).

####  IV-D3 The use-case for AMP challenge binaries

DARPA AMP challenges is about REs to patch a vulnerability regarding a weak
encryption algorithm where the encryption of communication traffic was
accomplished with a deprecated cipher suite, Triple DES or 3DES [49]. For this
challenge, REs have to analyze the vulnerable binary, identify functions and
instructions to be patched, 3DES cipher suite in this case, and patch 3DES-
related function calls and instructions with the ones for AES [50]. All these
steps happen at the decompiled binary level, and the vulnerable binaries are
optimized by a compiler and stripped of the debugging information and function
names. Furthermore, these binaries are sometimes statically linked against
libraries such as GNU C Library [51] or OpenSSL, which introduce many extra
functions to the binary (some of which will never be called/used). Given these
complications, it becomes a non-trivial task for an RE to make sense of all
these functions, find the problem, and successfully patch the problem. The
direct usage of our cfg2vec plugin was to pick a function of interest with
stripped information and see predictions of potential function names or
matching functions from the available reference binary to confirm that whether
this function is in the critical path during RE’s problem solving. As Figure 5
shows, our plugin allows users to see possible matches between functions from
a stripped vulnerable binary and functions from a patched (reference) binary
with extra information. REs may then leverage such information and make
appropriate notes for that function, allowing them to complete their jobs more
efficiently. The main feedback we received from REs who used the tool was that
this is the functionality REs would like to have. However, the accuracy and
usability of the tool were not high enough to truly utilize the tool’s
potential.

##  V Conclusion

This paper presents cfg2vec, a Hierarchical Graph Neural Network-based
approach for software reverse engineering. Building on top of Ghidra, our
cfg2vec plugin can extract a Graph-of-Graph (GoG) representation for binary,
combining the information from Control-Flow Graphs (CFG) and Function-Call
Graphs (FCG). Cfg2vec utilizes a hierarchical graph embedding framework to
learn the representation for each function in binary code compiled into
various architectures. Lastly, our cfg2vec utilizes the learned function
embeddings for function name prediction, outperforming the state-of-the-art
[18] by an average of 24.54% across all tested binaries. By increasing the
amount of data, our model achieved 51.84% better. While [18] requires training
once for each CPU architecture, our cfg2vec still can outperform consistently
across all the architectures, only with one training. Besides, our model
generalizes the learning better [18] to the binaries built from untrained CPU
architectures. Lastly, we demonstrate that our cfg2vec can assist the real-
world REs in resolving Darpa Assured MicroPatching (AMP) challenges.

## Acknowledgment

This material is based upon work supported by the Defense Advanced Research
Projects Agency (DARPA) and Naval Information Warfare Center Pacific (NIWC
Pacific) under Contract Number N66001-20-C-4024. The views, opinions, and/or
findings expressed are those of the author(s) and should not be interpreted as
representing the official views or policies of the Department of Defense or
the U.S. Government.

## References

  * [1] K. Zhidanov, S. Bezzateev, A. Afanasyeva, M. Sayfullin, S. Vanurin, Y. Bardinova, and A. Ometov, “Blockchain technology for smartphones and constrained iot devices: A future perspective and implementation,” in _2019 IEEE 21st Conference on Business Informatics (CBI)_ , vol. 2. IEEE, 2019, pp. 20–27.
  * [2] A. Panarello, N. Tapas, G. Merlino, F. Longo, and A. Puliafito, “Blockchain and iot integration: A systematic survey,” _Sensors_ , vol. 18, no. 8, p. 2575, 2018.
  * [3] S. Dange and M. Chatterjee, “Iot botnet: the largest threat to the iot network,” in _Data Communication and Networks_. Springer, 2020, pp. 137–157.
  * [4] S. R. Chhetri, J. Wan, and M. A. Al Faruque, “Cross-domain security of cyber-physical systems,” in _2017 22nd Asia and South Pacific design automation conference (ASP-DAC)_. IEEE, 2017, pp. 200–205.
  * [5] A. Sargolzaei, A. Abbaspour, M. A. Al Faruque, A. Salah Eddin, and K. Yen, “Security challenges of networked control systems,” in _Sustainable interdependent networks_. Springer, 2018, pp. 77–95.
  * [6] A. Barua, L. Pan, and M. A. A. Faruque, “Bayesimposter: Bayesian estimation based. bss imposter attack on industrial control systems,” in _Annual Computer Security Applications Conference_ , 2022, pp. 440–454.
  * [7] F-secure, “Attack landscape h1 2019,” 2019. [Online]. Available: https://blog-assets.f-secure.com/wp-content/uploads/2019/09/12093807/2019_attack_landscape_report.pdf
  * [8] “CVE-2014-0160.” Available from MITRE, CVE-ID CVE-2014-0160., Dec. 3 2013\. [Online]. Available: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-0160
  * [9] I. Ghafoor, I. Jattala, S. Durrani, and C. M. Tahir, “Analysis of openssl heartbleed vulnerability for embedded systems,” in _17th IEEE International Multi Topic Conference 2014_. IEEE, 2014, pp. 314–319.
  * [10] “The heartbleed vulnerability.” 2014. [Online]. Available: http://heartbleed.com/
  * [11] “Shellshock: All you need to know about the bash bug vulnerability,” 2014. [Online]. Available: https://www.symantec.com/
  * [12] “Shellshock in-depth: Why this old vulnerability won’t go away,” Security Intelligence, 2020. [Online]. Available: https://securityintelligence.com/articles/shellshock-vulnerability-in-depth/
  * [13] S.-H. Kim, M. A. Cohen, S. Netessine, and S. Veeraraghavan, “Contracting for infrequent restoration and recovery of mission-critical systems,” _Management Science_ , vol. 56, no. 9, pp. 1551–1567, 2010.
  * [14] N. S. Agency, “Ghidra - software reverse engineering framework.” 2019. [Online]. Available: https://www.nsa.gov/resources/everyone/ghidra/
  * [15] S. Hex-Rays, “Ida disassembler,” 2017.
  * [16] R. Team, _Radare2 Book_. GitHub, 2017\.
  * [17] A. Keliris and M. Maniatakos, “Icsref: A framework for automated reverse engineering of industrial control systems binaries,” _arXiv preprint arXiv:1812.03478_ , 2018.
  * [18] J. He, P. Ivanov, P. Tsankov, V. Raychev, and M. Vechev, “Debin: Predicting debug information in stripped binaries,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , 2018, pp. 1667–1680.
  * [19] J. Lacomis, P. Yin, E. Schwartz, M. Allamanis, C. Le Goues, G. Neubig, and B. Vasilescu, “Dire: A neural approach to decompiled identifier naming,” in _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2019, pp. 628–639.
  * [20] Y. David, U. Alon, and E. Yahav, “Neural reverse engineering of stripped binaries using augmented control flow graphs,” _Proceedings of the ACM on Programming Languages_ , vol. 4, no. OOPSLA, pp. 1–28, 2020.
  * [21] H. Gao, S. Cheng, Y. Xue, and W. Zhang, “A lightweight framework for function name reassignment based on large-scale stripped binaries,” in _Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2021, pp. 607–619.
  * [22] Q. Feng, R. Zhou, C. Xu, Y. Cheng, B. Testa, and H. Yin, “Scalable graph-based bug search for firmware images,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , 2016, pp. 480–491.
  * [23] X. Xu, C. Liu, Q. Feng, H. Yin, L. Song, and D. Song, “Neural network-based graph embedding for cross-platform binary code similarity detection,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 363–376.
  * [24] I. U. Haq and J. Caballero, “A survey of binary code similarity,” _arXiv preprint arXiv:1909.11424_ , 2019.
  * [25] K. Yakdan, S. Dechand, E. Gerhards-Padilla, and M. Smith, “Helping johnny to analyze malware: A usability-optimized decompiler and malware analysis user study,” in _2016 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2016, pp. 158–177.
  * [26] L. Ďurfina, J. Křoustek, and P. Zemek, “Psybot malware: A step-by-step decompilation case study,” in _2013 20th Working Conference on Reverse Engineering (WCRE)_. IEEE, 2013, pp. 449–456.
  * [27] M. J. Van Emmerik, _Static single assignment for decompilation_. University of Queensland, 2007.
  * [28] D. Brumley, J. Lee, E. J. Schwartz, and M. Woo, “Native x86 decompilation using semantics-preserving structural analysis and iterative control-flow structuring,” in _22nd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 13)_, 2013, pp. 353–368.
  * [29] “Binutils. (2019) objdump,” 2019. [Online]. Available: https://www.gnu.org/software/binutils/
  * [30] “Binary ninja. (2022) interactive disassembler, decompiler, and binary analysis platform,” 2022. [Online]. Available: https://binary.ninja/
  * [31] “Hopper. (2022) reverse engineering tool that lets you disassemble, decompile and debug your applications,” 2022. [Online]. Available: https://www.hopperapp.com/
  * [32] “Hex-rays. (2019) the hex-rays decompiler.” 2019. [Online]. Available: https://www.hex-rays.com/products/decompiler/
  * [33] M. Nyre-Yu, K. Butler, and C. Bolstad, “A task analysis of static binary reverse engineering for security,” Jan 2022. [Online]. Available: https://scholarspace.manoa.hawaii.edu/handle/10125/79608
  * [34] W. Shao, Q. Yang, X. Guo, and R. Cai, “A survey of available information recovery of binary programs based on machine learning,” in _2022 5th International Conference on Artificial Intelligence and Big Data (ICAIBD)_. IEEE, 2022, pp. 125–132.
  * [35] Z. L. Chua, S. Shen, P. Saxena, and Z. Liang, “Neural nets can learn function type signatures from binaries,” in _Proceedings of the 26th USENIX Conference on Security Symposium_ , ser. SEC’17. USA: USENIX Association, 2017, p. 99–116.
  * [36] U. Alon, M. Zilberstein, O. Levy, and E. Yahav, “Code2vec: Learning distributed representations of code,” _Proc. ACM Program. Lang._ , vol. 3, no. POPL, jan 2019. [Online]. Available: https://doi.org/10.1145/3290353
  * [37] F. Artuso, G. A. Di Luna, L. Massarelli, and L. Querzoni, “In nomine function: Naming functions in stripped binaries with neural networks,” _arXiv preprint arXiv:1912.07946_ , 2019.
  * [38] K. Redmond, L. Luo, and Q. Zeng, “A cross-architecture instruction embedding model for natural language processing-inspired binary code analysis,” _arXiv preprint arXiv:1812.09652_ , 2018.
  * [39] D. Vasan, M. Alazab, S. Venkatraman, J. Akram, and Z. Qin, “Mthael: Cross-architecture iot malware detection based on neural network advanced ensemble learning,” _IEEE Transactions on Computers_ , vol. 69, no. 11, pp. 1654–1667, 2020.
  * [40] M. Alhanahnah, Q. Lin, Q. Yan, N. Zhang, and Z. Chen, “Efficient signature generation for classifying cross-architecture iot malware,” in _2018 IEEE conference on communications and network security (CNS)_. IEEE, 2018, pp. 1–9.
  * [41] P. Goyal and E. Ferrara, “Graph embedding techniques, applications, and performance: A survey,” _CoRR_ , vol. abs/1705.02801, 2017. [Online]. Available: http://arxiv.org/abs/1705.02801
  * [42] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE transactions on neural networks and learning systems_ , 2020.
  * [43] R. Yasaei, S.-Y. Yu, and M. A. Al Faruque, “Gnn4tj: Graph neural networks for hardware trojan detection at register transfer level,” in _2021 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2021, pp. 1504–1509.
  * [44] S.-Y. Yu, A. V. Malawade, D. Muthirayan, P. P. Khargonekar, and M. A. Al Faruque, “Scene-graph augmented data-driven risk assessment of autonomous vehicle decisions,” _IEEE Transactions on Intelligent Transportation Systems_ , 2021.
  * [45] M. Hassen and P. K. Chan, “Scalable function call graph-based malware classification,” in _Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy_ , 2017, pp. 239–248.
  * [46] S. Harada, H. Akita, M. Tsubaki, Y. Baba, I. Takigawa, Y. Yamanishi, and H. Kashima, “Dual graph convolutional neural network for predicting chemical networks,” _BMC bioinformatics_ , vol. 21, pp. 1–13, 2020.
  * [47] J. Staff, “Assembled labeled library for static analysis research (allstar) dataset,” Dec 2019. [Online]. Available: https://allstar.jhuapl.edu/
  * [48] “Debian gnu linux installation guide,” 2004. [Online]. Available: https://www.debian.org/releases/bullseye/i386/ch02s01.en.html#idm186
  * [49] J. Callas, “Triple des: How strong is the data encryption standard?” May 2017\. [Online]. Available: https://www.techtarget.com/searchsecurity/tip/Expert-advice-Encryption-101-Triple-DES-explained
  * [50] C. Bernstein and M. Cobb, “What is the advanced encryption standard (aes)? definition from searchsecurity,” Sep 2021. [Online]. Available: https://www.techtarget.com/searchsecurity/definition/Advanced-Encryption-Standard
  * [51] T. Rothwell and J. Youngman, “The gnu c reference manual,” _Free Software Foundation, Inc_ , p. 86, 2007.


# Combinatorially Rich Sets in partial semigroups

Arpita Ghosh<EMAIL_ADDRESS>Research Fellow, Department of
Mathematics, University of Haifa, 3498838 Haifa, Israel

###### Key words and phrases:

Combinatorially Rich Sets, partial semigroups, Piecewise Syndetic sets,
algebra in Stone-Čech compactification.

Abstract. The notion of _combinatorially rich_ set was first introduced by V.
Bergelson and D. Glasscock. The goal of this paper is to study these subsets
in the setting of adequate partial semigroups and describes its connection
with the other concepts of large sets.

##  1\. Introduction

Many mathematicians discover abundant notions of large sets in $\mathbb{N}$ as
well as in any arbitrary semigroups by using the algebraic structure of the
Stone-Čech Compactification $\beta S$ of the discrete set $S.$ In [1],
Bergelson and Glasscock first introduced a new notion of large sets for a
commutative semigroup and discuss a _strong_ combinatorial structure of this.
In a recent article [3], Hindman et al. extend the definition of
_combinatorially rich_ sets to arbitrary semigroups and establish the
relationships of these sets to other notions of largeness in semigroups. In
this paper, we study combinatorially rich subsets in arbitrary adequate
partial semigroup and derive relationships between this kind of sets and other
notions of large sets in partial semigroups by using the algebraic structure
of Stone-Čech compactification.

We introduce a brief survey on algebraic structure of $\beta S$ (the Stone-
Čech compactification) for a discrete semigroup $(S,+)$. The elements of
$\beta S$ are ultrafilters on $S$, identifying the principal ultrafilters with
the points of $S$ and thus pretending that $S\subseteq\beta S$. Given
$A\subseteq S$ let us set,

$\overline{A}=\\{p\in\beta S:A\in p\\}.$

Then the set $\\{\overline{A}:A\subseteq S\\}$ is a basis for a topology on
$\beta S$ 111For the notation of closure of a subset $A$ we use both the
notation $\overline{A}$ and $\operatorname{cl}_{\beta S}(A)$ simultaneously..
The operation $+$ on $S$ can be extended to $(\beta S,+)$ in such a way that
it becomesxc a compact right topological semigroup (that is, for any
$p\in\beta S$, the function $\rho_{p}:\beta S\rightarrow\beta S$ defined by
$\rho_{p}(q)=q+p$ is continuous) with $S$ contained in its topological center
(meaning that for any $x\in S$, the function $\lambda_{x}:\beta
S\rightarrow\beta S$ defined by $\lambda_{x}(q)=x+q$ is continuous). Given
$p,q\in\beta S$ and $A\subseteq S$, $A\in p+q$ if and only if $\\{x\in
S:-x+A\in q\\}\in p$, where $-x+A=\\{y\in S:x+y\in A\\}$.

A nonempty subset $I$ of a semigroup $(T,+)$ is called a left ideal of T if
$T+I\subset I$, a right ideal if $I+T\subset I$, and a two-sided ideal (or
simply an ideal) if it is both a left and a right ideal. A minimal left ideal
is a left ideal that does not contain any proper left ideal. Similarly, we can
define the minimal right ideal and the smallest ideal.

Any compact Hausdorff right topological semigroup $(T,+)$ has a smallest two
sided ideal

$\begin{array}[]{ccc}K(T)&=&\bigcup\\{L:L\text{ is a minimal left ideal of
}T\\}\\\ &=&\,\,\,\,\,\bigcup\\{R:R\text{ is a minimal right ideal of
}T\\}.\end{array}$

Given a minimal left ideal $L$ and a minimal right ideal $R$, $L\cap R$ is a
group, and in particular, contains an idempotent. An idempotent in $K(T)$ is
called a minimal idempotent. If $p$ and $q$ are idempotents in $T$, we write
$p\leq q$ if and only if $p+q=q+p=p$. An idempotent is minimal with respect to
this relation if and only if it is a member of the smallest ideal. See [6] for
an elementary introduction to the algebra of $\beta S$ and any unfamiliar
details.

##  2\. Preliminaries on partial semigroups

In this section, we recall some definitions and results from a partial
semigroup context. For more details, the readers are referred to [6]. We start
with the following definition.

######  Definition 2.1.

(Partial semigroup) A partial semigroup is defined as a pair $(G,\ast)$ where
$\ast$ is an operation defined on a subset $X$ of $G\times G$ and satisfies
the statement that for all $x$, $y$, $z$ in $G$, $(x\ast y)\ast z=x\ast(y\ast
z)$ in the sense that if either side is defined, so is the other and they are
equal. A partial semigroup is commutative if ${x\ast y=y\ast x}$ for every
${(x,y)\in X}$.

Partial semigroups which arise naturally in our minds are as follows.

######  Example 2.2.

Any semigroup is an obvious example of a partial semigroup.

######  Example 2.3.

Let us consider ${G=\mathcal{P}_{f}({\mathbb{N}})}=\\{F\mid\emptyset\neq
F\subseteq\mathbb{N}$ and $F$ is finite$\\}$ and let ${X=\\{(\alpha,\beta)\in
G\times G\mid\alpha\cap\beta=\emptyset\\}}$ be the family of all pairs of
disjoint sets, and let ${\ast:X\rightarrow G}$ be the union. It is easy to
check that this is a commutative partial semigroup. We shall denote this
partial semigroup as $(\mathcal{P}_{f}({\mathbb{N}}),\uplus)$.

For a semigroup, it is known that there is a notion of compactification,
namely the Stone-Čech compactification, which is a compact right topological
semigroup. One can do a similar construction for any partial semigroup but
that won’t be a semigroup. To get a compact topological semigroup out of a
partial semigroup we recall the following definitions.

######  Definition 2.4.

Let $(S,\ast)$ be a partial semigroup.
(a) For $s\in S$, $\phi(s)=\\{t\in S\mid s\ast t$ is defined in $S\\}$.
(b) For $H\in\mathcal{P}_{f}(S)$, $\sigma(H)=\bigcap\limits_{s\in H}\phi(s)$.
(c) $(S,\ast)$ is adequate if and only if $\sigma(H)\neq\emptyset$ for all
$H\in\mathcal{P}_{f}(S)$.
(d) $\delta S=\bigcap\limits_{x\in S}\operatorname{cl}_{\beta
S}(\phi(x))=\bigcap\limits_{H\in\mathcal{P}_{f}(S)}\operatorname{cl}_{\beta
S}(\sigma(H))$. Here $\beta S$ denotes the Stone-Čech compactification of $S.$

So, the partial semigroup $(\mathcal{P}_{f}({\mathbb{N}}),\uplus)$ is
adequate. We are specifically interested in adequate partial semigroups as
they lead to an interesting subsemigroup $\delta S$ of $\beta S$, the Stone-
Čech compactification of $S$ which is itself a compact right topological
semigroup. Notice that adequacy of $S$ is exactly what is required to
guarantee that $\delta S\neq\emptyset$. If $S$ is, in fact, a semigroup, then
$\delta S=\beta S$.

Now we recall some of the basic properties of the operation $\ast$ in $\delta
S$.

######  Definition 2.5.

Let $(S,\ast)$ be a partial semigroup. For $s\in S$ and $A\subseteq S$,
$s^{-1}A=\\{t\in\phi(s)\mid s\ast t\in A\\}$.

######  Lemma 2.6.

Let $(S,\ast)$ be a partial semigroup, let $A\subseteq S$ and let $a,b,c\in
S$. Then $c\in b^{-1}(a^{-1}A)$ if and only if both $b\in\phi(a)$ and
$c\in(a\ast b)^{-1}A$. In particular, if $b\in\phi(a)$, then
$b^{-1}(a^{-1}A)=(a\ast b)^{-1}A$.

###### Proof.

[4, Lemma 2.3] ∎

######  Definition 2.7.

Let $(S,\ast)$ be an adequate partial semigroup.
(a) For $a\in S$ and $q\in\overline{\phi(a)}$, $a\ast q=\\{A\subseteq S\mid
a^{-1}A\in q\\}$.
(b) For $p\in\beta S$ and $q\in\delta S$, $p\ast q=\\{A\subseteq
S\mid\\{a^{-1}A\in q\\}\in p\\}$.

######  Lemma 2.8.

Let $(S,\ast)$ be an adequate partial semigroup.
(a) If $a\in S$ and $q\in\overline{\phi(a)}$, then $a\ast q\in\beta S$.
(b) If $p\in\beta S$ and $q\in\delta S$, then $p\ast q\in\beta S$.
(c) Let $p\in\beta S,q\in\delta S$, and $a\in S$. Then $\phi(a)\in p\ast q$ if
and only if $\phi(a)\in p$.
(d) If $p,q\in\delta S$, then $p\ast q\in\delta S$.

###### Proof.

[4, Lemma 2.7]. ∎

######  Lemma 2.9.

Let $(S,\ast)$ be an adequate partial semigroup and let $q\in\delta S$. Then
the function $\rho_{q}:\beta S\rightarrow\beta S$ defined by
$\rho_{q}(p)=p\ast q$ is continuous.

###### Proof.

[4, Lemma 2.8]. ∎

######  Lemma 2.10.

Let $p\in\beta S$ and let $q,r\in\delta S$. Then $p\ast(q\ast r)=(p\ast q)\ast
r$.

###### Proof.

[4, Lemma 2.9]. ∎

######  Definition 2.11.

For $A\in p$, define $A^{\ast}=\\{x\in A\mid x^{-1}A\in p\\}$.

Given an idempotent $p\in\delta S$, that is, $p\ast p=p\in\delta S$ and $A\in
p$, it is immediate that $A^{\ast}\in p$.

######  Lemma 2.12.

Let $p=p\ast p\in\delta S$, let $A\in p$, and let $x\in A^{\ast}$. Then
$x^{-1}A^{\ast}\in p$.

###### Proof.

[4, Lemma 2.12]. ∎

As a consequence of the above results, we have that if $(S,\ast)$ is an
adequate partial semigroup, then $(\delta S,\ast)$ is a compact right
topological semigroup. Being a compact right topological semigroup, $\delta S$
contains idempotents, left ideals, a smallest two-sided ideal, and minimal
idempotents [2]. Thus $\delta S$ provides a suitable candidate to study its
algebraic properties that relates the largeness notion for $S.$

In partial semigroup structure we need to know some definitions and lemmas
related with sequences in partial semigroups.

######  Definition 2.13.

Let $(S,\ast)$ be a partial semigroup and let $f$ be a sequence in $S.$ Then
$f$ is _adequate_ if and only if $\prod_{t\in H}f(t)$ is defined for each
$H\in\mathcal{P}_{f}(\mathbb{N})$ and for each $F\in\mathcal{P}_{f}(S),$ there
exists $m\in\mathbb{N}$ such that $FP(\langle
f(t)\rangle^{\infty}_{t=m})\subseteq\sigma(F).$

######  Definition 2.14.

For any $r\in\mathbb{N}$, $f:[r]\to S$ is called _adequately extendable
sequence_ if there exists $\widehat{f}\in\mathcal{T}$ (the set of all adequate
sequences in $S$) such that $\widehat{f}|_{[r]}=f.$

######  Definition 2.15.

A set $F\in\mathcal{P}_{f}(\mathcal{T})$ is a strongly adequate set if and
only if whenever $\phi\colon\mathbb{N}\rightarrow F$ and
$g\colon\mathbb{N}\rightarrow S$ is defined by, for $n\in\mathbb{N}$,
$g(n)=\phi(n)(n),$ then $g$ is an adequate sequence.

######  Lemma 2.16.

Assume that $(S,\ast)$ is a countable adequate partial semigroup and let
$F\in\mathcal{P}_{f}(\mathcal{T}).$ There is an increasing sequence
$\langle\delta(t)\rangle^{\infty}_{t=1}$ in $\mathbb{N}$ such that if for each
$f\in F$, $h_{f}\colon\mathbb{N}\rightarrow S$ is defined by, for
$n\in\mathbb{N}$, $h_{f}(n)=f(\delta(n)),$ then $\\{h_{f}\colon f\in F\\}$ is
a strongly adequate set.

###### Proof.

[5, Lemma 4.6] ∎

######  Lemma 2.17.

Let $(S,\ast)$ be an adequate partial semigroup. Let $f$ be an adequate
sequencein $S,$ and let $\langle H_{n}\rangle^{\infty}_{n=1}$ be a sequence in
$\mathcal{P}_{f}(\mathbb{N})$ such that $\max H_{n}<\min H_{n+1}$ for each
$n\in\mathbb{N}.$ Define $g\colon\mathbb{N}\rightarrow S$ such that for each
$n\in\mathbb{N}$, $g(n)=\prod_{t\in H_{n}}f(t).$ Then $g$ is an adequate
sequence in $S.$

###### Proof.

[5, Lemma 4.7]. ∎

Notations. We denote by $[n]=\\{1,2,\cdots,n\\}$ and $\sf Mat_{r\times k}(S)$
as the set of all $r\times k$-matrices over $S$ and $\widehat{\sf
Mat}_{r\times k(S)}$, a subset of $\sf Mat_{r\times k}(S)$, is a collection of
those matrices such that each column is adequately extendable sequence. Also,
we denote by

$\mathfrak{J}_{m}=\\{\textbf{t}\in\mathbb{N}^{m}|t(1)<t(2)<\cdots<t(m)\\}\mbox{
and }$
$\mathfrak{J}^{r}_{m}=\\{\textbf{t}\in\mathbb{N}^{m}|t(1)<t(2)<\cdots<t(m)\leq
r\\}.$

##  3\. Combinatorially rich sets

In [1] Bergelson and Glasscock introduced a new notion of large sets for a
commutative semigroup. Given an $r\times k$ matrix $M$ we denote by $m_{i,j}$
the element in row $i$ and column $j$ of $M.$

######  Definition 3.1.

Let $(S,+)$ be a commutative semigroup and let $A\subseteq S.$ Then $A$ is a
_combinatorially rich set_ (denoted by CR-set) if and only if for each
$k\in\mathbb{N},$ there exists $r\in\mathbb{N}$ such that whenever $M$ is an
$r\times k$ matrix with entries from $S,$ there exist $a\in S$ and nonempty
$H\subseteq\\{1,2,\cdots,r\\}$ such that for each $j\in\\{1,2,\cdots,k\\}$,
$a+\sum_{t\in H}m_{t,j}\in A.$

The authors of [1] noted that the _CR-set_ is intimately related to the notion
of $J$-sets those are key to characterizing $C$-sets, which has very rich
combinatorial properties.

Analogously, we can define combinatorially rich sets in commutative adequate
partial semigroups as follows.

######  Definition 3.2.

Let $(S,\ast)$ be a commutative adequate partial semigroup and let $A\subseteq
S.$ Then $A$ is called a $CR$-set if and only if for each $k\in\mathbb{N},$
there exists $r\in\mathbb{N}$ such that whenever $M\in\widehat{\sf
Mat}_{r\times k}(S)$ and $W\in\mathcal{P}_{f}(S),$ there exist $a\in S$ and
$H\subseteq\mathcal{P}_{f}([r])$ such that for all $j\in[k]$,
$a\ast\prod_{t\in H}m_{t,j}\in A\cap\sigma(W).$

The relationship between $J$-sets and $CR$-sets are more clearer from the
following equivalent lemma. To do that let us define the notion of adequately
extendable sequence in partial semigroups as follows.

######  Lemma 3.3.

Let $(S,\ast)$ be a commutative adequate partial semigroup and let $A\subseteq
S.$ Then the following statements are equivalent

  1. (a)

$A$ is a $CR$\- set in commutative adequate partial semigroups.

  2. (b)

For each $k\in\mathbb{N}$ there exists $r\in\mathbb{N}$ such that whenever
$F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k$ and
$L\in\mathcal{P}_{f}(S)$, there exist $a\in S$ and $H\in\mathcal{P}_{f}([r])$
such that for all $f\in F$, $a\ast\prod_{t\in H}f(t)\in A\cap\sigma(L).$

###### Proof.

Assume $(a)$ holds. Let
$G=\\{g_{1},g_{2},\cdots,g_{k}\\}\in\mathcal{P}_{f}(\mathcal{T}).$ Pick
$r\in\mathbb{N}.$ Let us construct a matrix

$M_{G}=\left[g_{1}|_{[r]}\colon g_{2}|_{[r]}\colon\cdots\colon
g_{k}|_{[r]}\right]\in\widehat{\sf Mat}_{r\times k}(S)$

where $m_{t,j}:=g_{j}|_{[r]}(t).$

Since $A$ is a $CR$-set, whenever $L\in\mathcal{P}_{f}(S)$, pick $a\in S$ and
$H\in\mathcal{P}_{f}([r])$ such that for all $j\in[k]$,

$a\ast\prod_{t\in H}g_{j}|_{[r]}(t)\in A\cap\sigma(L)$

and it turns out that $a\ast\prod_{t\in H}g_{j}(t)\in A\cap\sigma(L)$ for all
$j\in[k].$

Now we prove $(a)$ assuming $(b).$ Let $M\in\widehat{\sf Mat}_{r\times k}(S)$.
Then one can think off $M=[f_{1}\colon f_{2}\colon\cdots\colon f_{k}]$ where

$f_{j}\colon[r]\rightarrow S,\hskip 28.45274ptj=1,2,\cdots,k$

Now, since $f_{j}$ is adequately extendable sequence for each $i$, we can
consider $s^{0}_{j}:=\prod_{i=1}^{r}f_{j}(i)$ and
$\phi(s^{0}_{j})\neq\emptyset.$ Pick $s^{1}_{j}\in\phi(s^{0}_{j}).$ Therefore,
for the adequacy property we can again pick $s^{2}_{j}\in\phi(s^{0}_{j}\ast
s^{1}_{j})\subseteq\phi(s^{0}_{j})\cap\phi(s^{1}_{j})=\sigma(\\{s^{0}_{j},s^{1}_{j}\\}).$
Continuing this process, we can pick
$s^{n}_{j}\in\sigma(\\{s^{0}_{j},s^{1}_{j},\cdots,s^{n-1}_{j}\\}).$ Therefore,
we get an adequate sequence

$\widehat{f_{j}}=(f_{j}(1),f_{j}(2),\cdots,f_{j}(r),s^{0}_{j},s^{1}_{j},\cdots)\mbox{
in }S,$

for each $j=1,2,\cdots,k.$

So,
$\widehat{F}=\\{\widehat{f_{1}},\widehat{f_{2}},\cdots,\widehat{f_{k}}\\}\in\mathcal{P}_{f}(\mathcal{T})$
satisfying $|\widehat{F}|\leq k.$ Let $L\in\mathcal{P}_{f}(S).$ Pick $a\in S$
and $H\in\mathcal{P}_{f}([r])$ such that for all $\widehat{f}\in\widehat{F}$,

$a\ast\prod_{tinH}\widehat{f}(t)\in A\cap\sigma(L).$

Observe that $\widehat{f}(t)=f(t)$, $1\leq t\leq r$, i.e.,
$\widehat{f}(t)=f(t)$ for all $t\in H.$ Therefore,

$a\ast\prod_{t\in H}f(t)\in A\cap\sigma(L)\mbox{ for all }f\in F.$

Hence the result follows. ∎

As mentioned earlier, the $CR$-sets are intimately related to the notion of
$J$-sets, so we recall the definition of $J$-sets for adequate partial
semigroups.

######  Definition 3.4.

A set $A\subseteq S$ is a $J$-set if and only if for all
$F\in\mathcal{P}_{f}(\mathcal{T})$ and all $L\in\mathcal{P}_{f}(S)$, there
exist $m\in\mathbb{N}$, ${\bf a}\in S^{m+1}$, and ${\bf t}\in\mathfrak{J}_{m}$
such that for all $f\in F$, $(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in
A\cap\sigma(L).$

Similarly, the definition of combinatorially rich set in an arbitrary adequate
partial semigroup is based on the corresponding definition for $J$-sets which
is mentioned in 3.4.

######  Definition 3.5.

Let $(S,\ast)$ be an adequate partial semigroup. A set $A\subseteq S$ is a
$J$-set if and only if for all $F\in\mathcal{P}_{f}(\mathcal{T})$ and for all
$L\in\mathcal{P}_{f}(S),$ there exist $m\in\mathbb{N}$, ${\bf a}\in S^{m+1}$
and ${\bf t}\in\mathfrak{J}_{m}$ such that for all $f\in F$,
$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L).$

So, now we can define _combinatorially rich sets_ (aka CR-sets) in arbitrary
adequate partial semigroups.

######  Definition 3.6.

Let $(S,\ast)$ be an adequate partial semigroup and $A\subseteq S.$

  1. (a)

$A$ is a _CR set_ if and only if for each $k\in\mathbb{N}$ there exists
$r\in\mathbb{N}$ such that for each $F\in\mathcal{P}_{f}(\mathcal{T})$ with
$|F|\leq k$ and for all $L\in\mathcal{P}_{f}(S),$ there exist
$m\in\mathbb{N}$, ${\bf a}\in S^{m+1}$ and ${\bf t}\in\mathfrak{J}^{r}_{m}$
such that for all $f\in F$,

$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L).$

  2. (b)

Given $k\in\mathbb{N}$, $A$ is a _k-CR set_ if and only if there exists
$r\in\mathbb{N}$ such that for each $F\in\mathcal{P}_{f}(\mathcal{T})$ with
$|F|\leq k$ and for all $L\in\mathcal{P}_{f}(S),$ there exist
$m\in\mathbb{N}$, ${\bf a}\in S^{m+1}$ and ${\bf t}\in\mathfrak{J}^{r}_{m}$
such that for all $f\in F$,

$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L).$

######  Lemma 3.7.

Let $(S,\ast)$ be a commutative adequate partial semigroup and let $A\subseteq
S$. Then Lemma 3.3 (c) and Definition 3.6 (a) are equivalent.

###### Proof.

Let $A$ be a $CR$-set according to Definition 3.6 (a). For $k\in\mathbb{N}$
there exists $r\in\mathbb{N}$ such that for each
$F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k$ and for all
$L\in\mathcal{P}_{f}(S),$ there exist $m\in\mathbb{N}$, $\textbf{a}\in
S^{m+1}$ and $\textbf{t}\in\mathfrak{J}^{r}_{m}$ such that for all $f\in F$,
$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L)$. Given
$F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k$ and
$L\in\mathcal{P}_{f}(S)$, pick $m\in\mathbb{N}$, ${\bf a}\in S^{m+1},$ and
${\bf t}\in\mathfrak{J}^{r}_{m}$, let $\hat{a}=\prod_{i\in[m+1]}a(i)$ and
$H=\\{t(1),t(2),\cdots,t(m)\\}$. Then

$(\prod\limits_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L),$

and hence $\hat{a}\ast\prod_{t\in H}f(t)\in A\cap\sigma(L).$ Therefore $A$ is
a $CR$-set according to Lemma 3.3 (c).

For the necessary condition, let $A$ be a $CR$-set according to Lemma 3.3 (c).
Let $F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k$ be given. So, for
$f\in F,$ define

$g_{f}(j)=f(j)\ast f(r+j).$

Then the set $G=\\{g_{f}|f\in F\\}$ is a member of
$\mathcal{P}_{f}(\mathcal{T})$ with $|G|\leq k.$ Let $L\in\mathcal{P}_{f}(S)$,
so pick $b\in S$ and $H\in\mathcal{P}_{f}([r])$ such that for all $f\in F$ we
have

(1) $b\ast\prod_{t\in H}g_{f}(t)\in A\cap\sigma(L)\;(\mbox{due to Lemma
}\ref{creq}\mbox{ (c)}).$

Setting $H=\\{t(1)<t(2)<\cdots<t(m)\\}$ and

$a(j)=\begin{cases}b,&\mbox{if }j=1\\\ f(r+t(j-1)),&\mbox{if
}j\in\\{2,\cdots,m+1\\}.\end{cases}$

and then substituting in (1) we obtained

$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in A\cap\sigma(L).$

Hence the result follows. ∎

######  Theorem 3.8.

Let $(S,\ast)$ be a countable adequate partial semigroup and let
$A_{1},A_{2}\subseteq S.$ If $A=A_{1}\cup A_{2}$ is a $CR$-set in $S,$ then
either $A_{1}$ or $A_{2}$ is a $CR$-set in $S.$

###### Proof.

Assume that $A=A_{1}\cup A_{2}$ is a $CR$-set in $S$ and neither $A_{1}$ nor
$A_{2}$ is a $CR$-set in $S.$ For $i\in\\{1,2\\},$ pick $k(i)\in\mathbb{N}$
and $L_{i}\in\mathcal{P}_{f}(S)$ such that for every $r\in\mathbb{N}$ there
exists $F_{i}\in\mathcal{P}_{f}(\mathcal{T})$ such that $|F_{i}|\leq k(i)$ and

(2) $(\forall m\in\mathbb{N})(\forall{\bf a}\in S^{m+1})(\forall{\bf
t}\in\mathfrak{J}^{r}_{m})(\exists f\in F_{i})$

such that $(\prod_{j=1}^{m}a(j)f(t(j)))\ast a(m+1)\notin
A_{i}\cap\sigma(L_{i})$

Let $k=k(1)+k(2)$ and let $L=L_{1}\cup L_{2}$ and $F=F_{1}\cup F_{2}$.
Therefore, $|F_{1}\cup F_{2}|\leq k(1)+k(2)=k.$ Write
$F=\\{f_{1},f_{2},\cdots,f_{k}\\}.$ Using 2.16, pick an increasing sequence
$\langle\delta(n)\rangle_{n.\geq 1}$ in $\mathbb{N},$ and for each $i\in[k]$,
define $h_{i}:\mathbb{N}\rightarrow S$, by for $n\in\mathbb{N}$,
$h_{i}(n)=f_{i}(\delta(n)).$ Then $H=\\{h_{i}:i\in[k]\\}$ is a _strongly_
adequate set.

By [6, Theorem 14.8.1], we can pick $n\in\mathbb{N}$ such that whenever the
set $W_{n}([k])$ of length $n$ words over the alphabet set $[k]$ is
$2$-colored, there is a variable word $w(v)$ beginning and ending with a
constant and without successive occurrences of $v$ such that
$\\{w(l):l\in[k]\\}$ is monochromatic. For each $w=b_{1}b_{2}\cdots b_{n}\in
W_{n}([k])$, define $g_{w}:\mathbb{N}\rightarrow S$ by

$g_{w}(y)=\prod_{i=1}^{n}h_{b_{i}}(ny+i).$

Since $H$ is strongly adequate set, then the function $\psi$ defined by

$\psi(ny+i)=h_{b_{i}}(ny+i)$

for all $y\in\mathbb{N}$ and each $i\in\\{1,2,\cdots,n\\}$ is an adequate
sequence. By Lemma 2.17, $g_{w}$ is an adequate sequence for each $w\in
W_{n}([k]).$

Since $A=A_{1}\cup A_{2}$ is a $CR$-set and $\\{g_{w}:w\in
W_{n}([k])\\}\in\mathcal{P}_{f}(\mathcal{T})$ and let
$\alpha=k^{n}=|W_{n}([k])|.$ Pick $\beta\in\mathbb{N}$ such that for every
$G\in\mathcal{P}_{f}(\mathcal{T})$ (in our case, we consider $G=\\{g_{w}|w\in
W_{n}([k])\\}$) with $|G|\leq\alpha$,

$(\exists m\in\mathbb{N})(\exists{\bf a}\in S^{m+1})(\forall{\bf
t}\in\mathfrak{J}^{\beta}_{m})$

we have,

$(\prod\limits_{i=1}^{m}a(i)\ast g_{w}(t(i))\ast a(m+1)\in
A\cap\sigma(L)\mbox{ for all }g_{w}\in G.$

For $i\in\\{1,2\\}$, $n\beta+n$ is not big enough to serve as $r$ for $k(i)$
so pick $F_{i}\in\mathcal{P}_{f}(\mathcal{T})$ with $|F_{i}|\leq k(i)$ such
that

$(\forall m\in\mathbb{N}),(\forall{\bf a}\in S^{m+1})(\forall{\bf
t}\in\mathfrak{J}^{n\beta+n}_{m})$ $(\exists f\in
F_{i}),(\prod\limits_{i=1}^{m}a(i)\ast f(t(i))\ast a(m+1)\notin
A_{i}\cap\sigma(L_{i}).$

Now consider a $2$-coloring $\phi\colon W_{n}([k])\rightarrow\\{1,2\\}$ given
by

$\phi(w)=\begin{cases}1&\mbox{if }(\prod_{i=1}^{m}a(i)\ast g_{w}(t(i)))\ast
a(m+1)\in A_{1}\\\ 2&\mbox{otherwise.}\end{cases}$

Pick a variable word $w(v)$, beginning and ending with a constant and without
successive occurrences of $v$ such that $\phi$ is constant on
$\\{w(l):l\in[k]\\}$. Assume without loss of generality that $\phi(w(l))=1$
for all $l\in[k].$ That is, for all $l\in[k]$, $(\prod_{i=1}^{m}a(i)\ast
g_{w}(t(i)))\ast a(m+1)\in A_{1}$.

Let $w(v)=b_{1}b_{2}\cdots b_{n}$ where each $b_{i}\in[k]\cup\\{v\\},$ some
$b_{i}=v$, $b_{1}\neq v$, $b_{n}\neq v$, and if $b_{i}=v$, then $b_{i+1}\neq
v$. Let $r$ be the number of occurrences of $v$ in $w(v)$ and pick $L(1)$,
$L(2)$, $\cdots,$ $L(r+1)$ and $s(1),$ $s(2),$ $\cdots,$ $s(r)$ such that for
each $p\in[r]$, $\max L(p)<s(p)<\min L(p+1)$,

$\bigcup_{p=1}^{r+1}L(p)=\\{i\in[n]:b_{i}\in[k]\\}\mbox{ and
}\\{s(1),s(2),\cdots,s(r)\\}=\\{i\in[n]:b_{i}=v\\}.$

We shall show that, given $y\in\mathbb{N},$ there exist ${\bf c_{y}}\in
S^{r+1}$ and $z_{y}(1)<z_{y}(2)<\cdots<z_{y}(r)$ such that for all $l\in[k]$,

$g_{w(l)}(y)=\prod_{i=1}^{r}c_{y}(i)\ast h_{l}(z_{y}(i)))\ast c_{y}(r+1)$

and further, for each $y$, $z_{y}(r)<z_{y+1}(1)$. So, let $y\in\mathbb{N}$ be
given. For $p\in[r+1]$, let $z_{y}(p)=ny+s(p).$ To see that these are as
required, first note that $z_{y}(r)=ny+s(r)\leq ny+n<z_{y+1}(1).$ Now let
$l\in[k]$ be given. Then $w(l)=d_{1}d_{2}\cdots d_{n}$, where for $i\in[n]$,

$d_{i}=\begin{cases}b_{i},&\mbox{ if }i\in\bigcup_{p=1}^{r+1}L(p)\\\ l,&\mbox{
if }i\in\\{s(1),s(2),\cdots,s(r)\\}.\end{cases}$

Therefore,

$\begin{array}[]{rl}g_{w(l)}(y)=&\prod\limits_{i=1}^{n}h_{d_{i}}(ny+i)\\\
=&(\prod\limits_{p=1}^{r}(\prod\limits_{i\in L(p)}h_{b_{i}}(ny+i))\ast
h_{l}(ny+s(p)))\ast\prod\limits_{i\in{L(r+1)}}h_{b_{i}}(ny+i)\\\
=&(\prod\limits_{p=1}^{r}c_{y}(p)\ast h_{l}(z_{y}(p)))\ast
c_{y}(r+1)\end{array}$

Therefore, our claim is satisfied. Next we claim that there exists
$u\in\mathbb{N}$ such that ${\bf d}\in S^{u+1}$ and
$(q(1),q(2),\cdots,q(u))\in\mathfrak{J}^{n\beta+n}_{u}$ and for each
$l\in[k]$,

(3) $(\prod_{j=1}^{m}a(j)\ast g_{w(l)}t(j))\ast
a(m+1)=(\prod_{i=1}^{u}d(i)\ast h_{l}(q(i)))\ast d(u+1).$

To justify the above claim, set $u=mr.$ For $j\in[m]$ and $p\in[r],$ let
$q((j-1)r+p)=z_{t(j)}(p).$ Thus one observes

$q(1)<q(2)<\cdots<q(u)=z_{t(m)}(r)=nt(m)+s(r)<nt(m)+n\leq n\beta+n.$

and hence $(q(1),q(2),\cdots q(u))\in\mathfrak{J}^{n\beta+n}_{u}.$ For
$j\in[m]$ and $p\in[r]\setminus[1]$, let $d((j-1)r+p)=c_{t(j)}(p).$ Let
$d(1)=a(1)\ast c_{t(1)}(1),$ let $d(u+1)=c_{t(m)}(r+1)\ast a(m+1)$ and for
$j\in[m-1],$ let $d(jr+1)=c_{t(j)}(r+1)\ast a(j+1)\ast c_{t(j+1)}(1).$

Note that ${\bf d}=(d(1),\cdots,d(u+1))\in S^{u+1}$ and for $l\in[k]$,

$\begin{array}[]{rl}(\prod\limits_{i=1}^{m}a(i)\ast g_{w(l)}(t(i)))\ast
a(m+1)=&(\prod\limits_{i=1}^{m}a(i)\ast(\prod\limits_{p=1}^{r}c_{t(i)}(p)\ast
h_{l}(z_{t(i)}(p)))\ast c_{t(i)}(r+1)))\ast a(m+1)\\\
=&(\prod\limits_{i=1}^{u}d(i)\ast h_{l}(q(i)))\ast d(u+1).\end{array}$

Therefore, we have $u\in\mathbb{N}$, ${\bf d}\in S^{u+1}$ and
$(q(1),q(2),\cdots,q(u))\in\mathfrak{J}^{n\beta+n}_{u}$, and hence

$(\delta(q(1)),\delta(q(2))),\cdots,\delta(q(u))))\in\mathfrak{J}^{\delta(n\beta+n)}_{u}$

as $\delta$ is an increasing sequence as defined in 2.9.

Using (3) and the discussion of an application of Hales-Jewett theorem, we
obtained that

$(\prod_{i=1}^{u}d(i)\ast h_{l}(q(i)))\ast d(u+1)=(\prod_{i=1}^{m}a(i)\ast
g_{w(l)}(t(m)))\ast a(m+1)\in A_{1}\cap\sigma(L)\subseteq
A_{1}\cap\sigma(L_{1}).$

On the other hand, by the assumption as in (2), we have

$(\prod_{i=1}^{u}d(i)\ast h_{l}(q(i)))\ast d(u+1)=(\prod_{i=1}^{u}d(i)\ast
f_{l}(\delta(q(i)))\ast d(u+1)\notin A_{1}\cap\sigma(L_{1}).$

for some $f_{l}\in F_{1}=\\{f_{1},\cdots,f_{k}\\}.$ This is a contradiction.
Hence the result follows. ∎

######  Definition 3.9.

Let $(S,\ast)$ be an adequate partial semigroup.

$CR(S)=\\{p\in\delta S:(\forall A\in p)(A\text{ is a CR-set})\\}$

For $k\in\mathbb{N}$, $k\mbox{-}CR(S)=\\{p\in\delta S:(\forall A\in p)(A\text{
is a k-CR set})\\}$

######  Theorem 3.10.

Let $(S,\ast)$ be a countable adequate partial semigroup. Then $CR(S)$ is a
compact two sided ideal of $\delta S$ and for each $k\in\mathbb{N}$,
$k$-$CR(S)$ is a compact two -sided ideal of $\delta S.$

###### Proof.

By Theorem 3.8 and [6, Theorem 3.11], $CR(S)\neq\emptyset.$ Since
$CR(S)\neq\emptyset$ and $CR(S)=\bigcap_{k=1}^{\infty}k\mbox{-}CR(S),$ we have
that each $k$-$CR(S)\neq\emptyset$ and it suffices to show that each
$k$-$CR(S)$ is a two-sided ideal of $\delta S,$ so let $k\in\mathbb{N}.$

Let $p\in k$-$CR(S)$ and let $q\in\delta S.$

Claim: $qp\in k$-$CR(S)$ and $pq\in k$-$CR(S).$

Let $A\in qp$ and let $B=\\{x\in S:x^{-1}A\in p\\}.$ Now $A\in qp.$ This
implies $\\{x\in S:x^{-1}A\in p\\}\in q.$ Therefore, $B\in q.$ Now $B\in q$
and $\sigma(W)\in q$ for any $W\in\mathcal{P}_{f}(S).$ So, $B\cap\sigma(W)\in
q$. Pick $x\in B\cap\sigma(W)$. This implies $x^{-1}A\in p.$ Now since $p\in
k$-$CR(S),$ then $x^{-1}A$ is a $k$-$CR$ set. So pick $r\in\mathbb{N}$ such
that for each $F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k,$ and for all
$W\in\mathcal{P}_{f}(S),$ there exist $m\in\mathbb{N}$, ${\bf a}\in S^{m+1}$
and ${\bf t}\in\mathfrak{J}^{r}_{m}$ such that $a(1)\ast f(t(1))\ast a(2)\ast
f(t(2))\ast\cdots\ast a(m)\ast f(t(m))\ast a(m+1)\in x^{-1}A\cap\sigma(W\ast
x).$ Therefore, $x\ast(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in
A\cap\sigma(W).$

Let $F\in\mathcal{P}_{f}(\mathcal{T})$ with $|F|\leq k$ and pick $m,{\bf a}$
and ${\bf t}\in\mathfrak{J}^{r}_{m}$ as guaranteed for $x^{-1}A.$ Define
$\textbf{b}\in S^{m+1}$ by $b(1)=x\ast a(1)$ and for
$j\in\\{2,3,\cdots,m+1\\}.$ Let $b(j)=a(j).$ Then for each $f\in F,$
$(\prod_{i=1}^{m}b(i)\ast f(t(i)))\ast b(m+1)\in A\cap\sigma(W).$ Therefore
$A$ is also a $k$-$CR$ set. Therefore, $qp\in k$-$CR.$

To see that $pq\in k$-$CR,$ let $A\in pq.$

Claim: $A$ is a $k$-$CR$ set.

Let $B=\\{x\in S:x^{-1}A\in q\\}.$ Then $B\in p.$ Therefore, $B$ is a $k$-$CR$
set.

Pick $r\in\mathbb{N}$ such that for each $F\in\mathcal{P}_{f}(\mathcal{T})$
with $|F|\leq k,$ and for all $W\in\mathcal{P}_{f}(S),$ there exist
$m\in\mathbb{N}$, ${\bf a}\in S^{m+1},$ and ${\bf t}\in\mathfrak{J}^{r}_{m}$
in $\mathbb{N}$ such that for each $f\in F$,

$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\in B\cap\sigma(W).$

Let $z_{f}=(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1).$ Therefore, $z_{f}\in
B\cap\sigma(W)$ for each $f\in F.$ Let $Z=\\{z_{f}:f\in F\\}$ and $L=W\ast Z.$
Since $z_{f}\in B$ for each $f\in F.$ This implies $z_{f}^{-1}A\in q$ for each
$f\in F.$ So, $\bigcap_{f\in F}z_{f}^{-1}A\in q.$ So pick $b\in\bigcap_{f\in
F}z_{f}^{-1}A\cap\sigma(L)\subseteq\bigcap_{f\in F}z_{f}^{-1}A\cap\sigma(W\ast
Z).$ Hence, $z_{f}\ast b\in A\cap\sigma(W).$

$(\prod_{i=1}^{m}a(i)\ast f(t(i)))\ast a(m+1)\ast b\in A\cap\sigma(W).$ Define
$\textbf{b}\in S^{m+1}$ by $b(j)=a(j)$ for $j\in\\{1,2,\cdots,m\\}$ and
$b(m+1)=a(m+1)\ast b.$ Then for each $f\in F$,

$(\prod_{i=1}^{m}b(i)\ast f(t(i)))\ast b(m+1)\in A\cap\sigma(W).$

Hence the result follows. ∎

######  Corollary 3.11.

Let $(S,\ast)$ be a countable adequate partial semigroup. A subset $A$ of $S$
is $CR$-set if and only if $CR(S)\cap\overline{A}\neq\emptyset.$

###### Proof.

The necessary part is trivial.

The other direction of the statement follows from Theorem 3.8 and [6, Theorem
3.11]. ∎

######  Definition 3.12.

Let $(S,\ast)$ be an adequate partial semigroup and let $A\subseteq S.$ The
set $A$ is piecewise syndetic set if and only if $\overline{A}\cap K(\delta
S)\neq\emptyset.$

######  Theorem 3.13.

Let $(S,\ast)$ be a countable adequate partial semigroup and let $A$ be a
piecewise syndetic subset of $S.$ Then $A$ is a $CR$-set.

###### Proof.

By Theorem 3.10, $CR(S)$ is a two-sided ideal of $\delta S,$ so $K(\delta
S)\subseteq CR(S).$ $A$ is piecewise syndetic set, so $\overline{A}\cap
K(\delta S)\neq\emptyset,$ so $\overline{A}\cap CR(S)\neq\emptyset.$ So we can
apply Corollary 3.11 and hence $A$ is a $CR$-set. ∎

## References

  * [1] V. Bergelson and D. Glasscock, _On the interplay between additive and multiplicative largeness and its combinatorial applications_ , J. Combin. Theory Ser. A 172(2020), 105203
  * [2] R. Ellis, _Distal transformation groups._ Pacific J. Math. 8 (1958), 401–405
  * [3] N. Hindman, H. Hosseini, D. Strauss, and M. Tootkaboni, _Combinatorially rich sets in arbitrary semigroups_ , Preprints
  * [4] N. Hindman and R. McCutcheon _VIP systems in partial semigroups_ , Discrete Math. 240 (2001), 45-70.
  * [5] N.Hindman and K.Pleasant, _Central sets theorem for arbitrary adequate partial semigroups_ , Topology Proc. 58 (2021), 183–206.0
  * [6] N. Hindman and D. Strauss, _Algebra in the Stone-Čech compactification: theory and applications, second edition_ , W. de Gruyter and Co., Berlin, 2012