Android-COCO: Android Malware Detection with Graph Neural Network for Byte- and Native-Code

With the popularity of Android growing exponentially, the amount of malware has significantly exploded. It is arguably one of the most viral problems on mobile platforms. Recently, various approaches have been introduced to detect Android malware, the majority of these are either based on the Manifest File features or the structural information, such as control flow graph and API calls. Among those methods, nearly all of them only consider the Java byte-code as the target to detect malicious behaviors. However, Recent research and our own statistics show that native payloads are commonly used in both benign and malicious apps. Current state-of-the-art Android static analysis tools avoid handling native method invocation. None of those tools have the capability to capture the inter-language behaviors. In this work, we explore an ensemble mechanism, which presents how the combination of byte-code and native-code analysis of Android applications can be efficiently used to cope with the advanced sophistication of Android malware. We, therefore, present a multi-layer approach that utilizes deep learning, natural language processing (NLP), as well as graph embedding techniques to handle the threats of Android malware, both from the Java byte-code and native code. After that, we design an ensemble algorithm to get the final result of malware detection system. To be specific, the first layer of our detection approach operates on the byte-code of application and the native code level, whereas the second layer focuses on the ensemble algorithm. Large-scale experiments on 100,113 samples (35,113 malware and 65,000 benign) show that only byte-code sub-system yields 99.8% accuracy and native-code sub-system yields an accuracy of 96.6%, whereas the Android-COCO method attains an accuracy of 99.86% which outperforms various related works.

I. INTRODUCTION
The mobile phone has become a necessity in our daily life. Due to its versatility, smartphone usage has grown exponentially to reach various sectors like social networks, ecommerce and banking. According to statistics on mobile OS market shares [1], Android is the world's dominant mobile operating system, leading the market with over 83% market share in comparison to iOS and Windows. Android's enormous dominance is largely a function of being open source as well as providing users with a rich store that involves millions of various applications. Further, the brisk prosperity of smartphones along with Android's huge popularity has not gone disregarded by malware authors. Rather, Android has become an attractive platform for launching thousands of malicious applications. Recently, the number of malware has increased by leaps and bounds to reach a disturbing level. Based on McAfee's report [2], the number of discovered Android malware has touched 3.5 millions in 2021, and each more there are around 300,000 new Android malware, which has led the overall mobile malware's tally to reach 25 millions.
To defend against the threat and mitigate the alarming spread of malware, several anti-virus scanners have been provided by computer security companies such as Symantec and McAfee. Many of these products use either signaturebased [3] or code matching [4] methods. Unfortunately, these techniques have proved their incapability to keep pace with the sophistication of malware. Hence, Android malware detection has been, and still is of the essence for security researchers in both industry and academia.
In recent years, various research works [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17] have been proposed to detect malware based on machine learning and deep learning techniques. The majority of these approaches use either Android application's attributes collected from the Manifest File, specifically, Permissions, Intent-filters, and Providers. Unfortunately, these approaches can be easily bypassed by certain obfuscation techniques, such as Identifier Renaming, Code Hiding, Reflection, Dead-Code Insertion or Instruction Substitution [18] 1 . All these obfuscation methods aim to alter the application's appearance but preserve its behavior, either by encrypting the values of packages and classes or embedding useless instructions to the program [19]. In a nutshell, while these Manifest-based detection approaches offer a supplementary security control to Android, they demonstrate failure against obfuscated applications. Accordingly, some approaches go one step further by considering the source code. Researchers have figured out that the high-level properties of the code, in particular, the code structure, such as the Function Call Graph (FCG) and API calls robust against obfuscation [20], [18].
Although some of aforementioned works, like Amandroid [5], flowdroid [6], yield high accuracy results, they operate solely on the DEX bytecode, which does not lead to a thorough analysis of Android applications. A recent study shows that 86% of Android applications involve native code, allowing this latter to be a reasonable threat vector [21]. That is to say, an application with a malicious embedded native code will go undetected by a layer that merely focuses on the DEX bytecode. This motivates the need for a byte-code and native-code combination approach that characterize and generalize the malicious patterns embedded in Android apps.
In this paper, we design an ensemble algorithm to combine the byte-code and native-code malware detection subsystems(or layers). In particular, we present a layered approach that blends the structural and inter-language analysis of Android applications. To this end, our approach consists of two layers, the graph-based detection layer and the ensemble layer. For the graph-based detection layer, it includes two subsystems: • Byte-code sub-system: It is based on the DEX bytecode. It first extracts the Program Dependence Graph 1 [18] considers native code as a type of obfuscation. However, we separate it from general obfuscation techniques in Android and we mention it in the following (PDG) of the Android application, and then employs an efficient graph embedding to transform the graph's main features to vectors, which is used as an input for our neural network. In an evaluation with 100,113 samples (35,113 malware and 65,000 benign), our structural-based approach is shown to be immensely efficient, as it yields an accuracy of 99.8%, which outperforms numerous existing works. • Native-code sub-system: It is based on the native code (.so files). It employs the graph embedding technique to transform the dynamic libraries (.so files) to vectors, which is then used to feed our network-based classifier.
Large scale experiments on the used datasets result in an accuracy rate of 96.66%. After the detection sub-systems, we design an ensemble algorithm as our second-layer, which combines the output of the two MLP classifiers.
• Using the ensemble algorithm, we improve the accuracy to 99.86%. In summary, our primary contributions are described as follows: • we introduce the graph embedding to Android malware detection. We present a novel approach that employs graph embedding technology to differentiate between benign and malicious applications. We encode either the Program Dependence Graph (PDG) and function call graph(FCG) into its own vector representations. The graph's embedding captures the graph topology and hence covers every layer's specific features. To the extent of our knowledge, this is the first work that consider both the byte-code and native-code to detect Android malware. • we use ensemble algorithm to combine the results of Android malware detection We present a multilayer approach that couples byte-code and native-code analysis from two different application components. The complementary strengths among the analysis of byte-code and native code's structure creates a thorough detection system.

II. BACKGROUND
In this section, first, we throw the lights on the architecture of Android applications and the existing android malware detection techniques. Then, we introduce the used Natural Language Processing concepts, namely the embedding techniques as well as graph neural network.

A. Android Package Kit (APK)
Android applications are deployed in the form of Application Package Kit (APK), which is a zipped file that involves the app's code in the DEX file format, native libraries, resources, assets and AndroidManifest.xml file. As for the DEX file, it involves the application's code. As mentioned earlier, Android uses Dalvik virtual machine to execute applications. Hence, it uses Dalvik bytecode instead of Java bytecode. At first, the Java source code is compiled to Java bytecode by a Java compiler, which is then compiled to Dalvik bytecode by the DEXcompiler. A DEX file contains classes definitions, each class involves one or more methods'(functions') definitions. Each method(function) comprises of one or more basic block, which involves one or multiple instructions. As for the instruction's format, it consists of a single opcode and multiple operands. In overall, Dalvik has 256 opcodes. Android applications make use of 222 opcodes as the others are reserved for future usage [22].

B. Program Dependence Graph
A Program Dependence Graph(PDG) is a graph that explicitly considers both data and control dependencies. Data dependence graph(DDG) represents the program's appropriate data flow whereas the control dependence graph (CDG) illustrates the program's control flow relationships. The combination of both dependencies covers all the program's computational parts, which leads to an efficient use when it comes to programs' optimizations. As for the graph's topology, Program Dependence Graph's nodes are represented as statements or instructions, while the edges represent both the data values and control conditions necessary to the execution of the node's operations [23]. The PDG of a program P is the union of a pair of graph: the DDG of P and the CDG of P. Note that the DDG and CDG are subgraphs of a PDG. The PDG is obtained by merging the DDG and the CDG [24].

C. Word, Sentence and Document Embedding
Adapting real life scenarios into machine learning models entails the mapping of textual inputs or scripts into numerical representation that is semantically expressive. Further, to ensure a good representation of a text input, the numerical representation should catch the linguistic sense of every word in the dataset. To be more specific, an informative numerical representation can enormously impact the performance of the model. There exists several natural language processing techniques to handle text data, such as word embedding [25], [26], sentence embedding [27], and document embedding [26].
• Word Embedding: It is a numeric vector representation, obtained by embedding semantic meanings of words from a particular corpus. Word2Vec is a technique to build such an embedding based on neural network. Word2Vec can be achieved through two techniques which employ neural network. Namely, Skip-Gram and Common Bag Of Words (CBOW). Skip-Gram learns the prediction of a target word based on its neighbors, whereas CBOW uses the context to predict a target word [25], [26]. • Sentence Embedding: It follows the same concept as word embedding. It represents a sentence with a numeric vector representation. A direct and frequently used approach for embedding sentences into a vector space is to aggregate the embedding vectors of the words forming a sentence [27]. • Document Embedding: It is an extension to Word2Vec.
Word2vec learns to represent a given word to its numeri-cal vector representation whereas Doc2Vec aims at representing a document into its numerical vector space [26].

D. Graph Embedding
Nowadays, a graph is considered to be a rich input for analysis works. It has been commonly applied in various fields. Further, feeding a machine learning model with graphs is very challenging. Here, the graph embedding comes in handy and acts as a technique that turns the graph's properties to a set of numeric vector representations to feed a particular model. The rich the graph embedding is, the good the results can be achieved. Thus, the embedding should catch all the graph's significant information, which involve its topology, vertex-tovertex relationships, and vertices.
Graph embedding can be categorized into the following two types [28]. The first one is node embedding, which is used to perform either classification or prediction tasks on vertexlevel. There exist numerous works that deal with the node embedding area, such as Deepwalk [29], Node2vec [30]and Graph Convolutional Networks (GCN) [31]. Meanwhile, the other is graph embedding, which is suitable when it comes to performing classification or prediction on a graph level. There are several techniques that can be adopted to perform graph embedding, such as Structure2Vec [32] and Graph2Vec [33].

III. MOTIVATION
As we mentioned above, there are many works in the Android Malware Detection field, however, nearly all of works are concentrating on the Android Byte-code, which includes the functional behavior writing in Java language. Currently, there are more and more Android application embeds native libraries (written in C and C++ language) in them and the trend to detect and categorize Android apps becomes significant.
Therefore, on the one hand, we need a methodology which is not only able to detect Android malware byte-code level, but also native code level.
On the other hand, since the platforms to support Android OS and its ecosystem are multiple, and many IV. SYSTEM DESIGN Our system follows the principle of Detection In-Depth [34], which is a security strategy that protects an asset by implementing multiple layers of detection to avoid a single point of failure. In our context, to defend against the Android malware threat, we placed two detection models (sub-systems) that vary in terms of focus.
To be precise, our first layer operates on the application's structural information, including byte-code sub-system and native code sub-system, whereas the second layer concentrates on the ensemble algorithm to combine the two subsystems of the first layer. The advantage of coupling two detection layers is to ensure an extensive examination of different application's components. Additionally, our multilayer approach deals merely with applications that involve native code. Regarding our system's output, an application with native code is considered to be benign only if both subsystems of the first layer prove its benignity. Otherwise, it is considered a malware. For applications without native code, the classification result is fully based on the byte-code subsystem's analysis.
We formalize our two-layer malware detection system as a binary classification problem. In the first layer, we define the graph sets, which represents the structural information of the executable files and native libraries (malware and benign), as our input, like G D (V D , E D ), where V D presents the set of graph's nodes, and E D presents the edges among those nodes and D presents the number of graph. For each graph g i (g ib and g in ), it is encoded as g i (V, X, A), where A ∈ {0, 1} m * n is the adjacency matrix and m is the number of the graph's node, The goal of the first layer of our system is to learn a mapping from the G D to Y D , f : G → Y to predict whether an executable file or a native library is malicious or not. The prediction function f can be learned by minimizing the loss function in Eq. 1. For the second layer, we use the logic gates ensemble to combine the results of two classifiers in the first layer. We will implement for formalized model in the following, where g i (g ib and g in ) in Eq. 1 is our graph embedding and f (f b and f n ) in Eq. 1 is our MLP-classifier(we use two MLP classifiers).

A. Byte-code based Malware Detection
The first subsystem of our approach deals with the DEX bytecode. We designed our first subsystem to deal with the DEX bytecode of Android applications. Accordingly, to obtain the main features of the DEX bytecode, we need to get the execution paths that fully covers the program. Unfortunately, with traditional analysis, this could hardly be achieved. As a result, graph-based techniques have been introduced, as they produce rich data representations. Contrary to early graphbased malware detection approaches that employed control flow and function call graphs to detect obfuscated parts of the code, our approach utilizes the Program Dependence Graph (PDG), which applies both data and control analysis. To put it differently, a PDG combines an explicit representation of data and control flow relationships of an Android application, which exposes the full program structure. Although malware variants vary in terms of code appearance due to obfuscation, they share one common program structure, which can be plainly observed by analyzing their PDGs. As illustrated in Figure 1, the structural byte-code subsystem is a five-step process. After the application's disassembling, we encoded every basic block to its corresponding vector and extracted the PDG. Next, we converted the entire PDG to a numerical vector of real numbers to feed our neural network. 1) Opcode Embedding: As described in Section II-A, Android applications are developed in Java and utilize a Dalvik virtual machine to execute. That is to say, an application's source code is first compiled to Java bytecode, then translated to Dalvik bytecode and saved in DEX. In the first subsystem of our malware detection approach, our aim is to tackle the DEX bytecode using the PDG, which models both control and data flow relationships. Consequently, after the disassembling phase, we merely considered Dalvik executable files. Further, capturing the PDG's topology requires handling both control and data dependencies found in an application. To this end, we treated every basic block of an application as a node. Additionally, we considered edges to express links bridging values' definitions and their uses to ensure a broad coverage of all the application's methods. Before casting the lights on the opcode embedding phase, it is important to understand the format of a basic block, which is a series of sequential instructions that are executed consecutively with no jumps in the middle [35]. A basic block can involve one or more instructions. Each instruction is composed of two elements, opcode, and operand. Our aim is to capture the context of every instruction in a basic block. Thus, we embedded each instruction to its corresponding vector.
We used opcode as an our input to build our corpus of vectors using the Word Embedding technique. Regarding the implementation of this step, we first built a large unsupervised corpus of opcodes extracted from our datasets. To this end, we used Androguard to retrieve an application's set of opcodes. Androguard has a function AnalyzeAPK that returns three objects, precisely, an Apk object, an array of DalvikVMFormat and Analysis object. Each object has its purpose. The Apk object involves all the contextual information of an application, such as package name and permissions. As for the DalvikVM-Format, it corresponds to the DEX files in an Apk. As for the Analysis object, it provides all the details of classes, methods, and fields found in an Apk. In this context, we used the DEX object, as it provides all the details related to classes, methods, and fields. For every method in an application, we retrieved all its instructions' opcodes. Next, for mapping each opcode to a vector of real numbers, we used Word2Vec [25] model with skip-gram method. To be specific, we tried to predict each word's context given a specific opcode. As defined in Section II-C, Word2Vec is an implementation technique of word embedding technology. It employs a neural network with one hidden layer to vectorize words. To implement the Word2Vec model, we used TensorFlow library [36] which provides a rich set of features that allow users to express data computation in an easy fashion. As parameters, we set the embedding size to be 64 and the window length to 1, as we wanted to take only one word in the chain.
2) Basic Block Embedding: After mapping every instruction's opcode into a single vector. We encoded each basic block to its corresponding vector by taking the mean of all its instructions' vectorial representations. In this step, we directly averaged all opcode embedding occurred in a basic block. Assuming each basic block BB includes n-opcode and each opcode is represented by a l-dimensional vector.
The output of the basic block embedding step is one single vector that represents a node.
3) Program Dependence Graph Construction: After mapping each vector to its corresponding vectorial representation, we constructed the program dependence graph for every application in our datasets. As mentioned before, every basic block in an application constitutes a node in its program dependence graph. Accordingly, for every basic block in a method, we vectorized it by averaging of all its instructions' vectors. We extract our program dependence graph with the assistance of Androguard. Further, we built edges by bridging every basic block to its related children. To this end, we used NetworkX [37], a python library for the creation and manipulation of networks. Further, in a network, two nodes should not have the same naming. To be precise, every node in a graph should have a unique name. In the context of machine language, instructions tend to be repetitive, which may lead to disregarding many nodes. Assuming a method has 2 basic blocks with the following opcodes: B 1 = B 2 = {const, move, goto}, the graph will disregard B 2 , as the encoding of both basic blocks is identical. To avoid this obstacle, we considered two sections in a node's construction, one for the embedding vector, whereas the other for its identifier. Therefore, for every basic block, we selected its parents' details, mainly the corresponding class and method descriptions.
4) Program Dependence Graph Embedding: Consequently, after the program dependence graph's construction, we transformed the entire graph to a vector of real numbers. To this end, we used Structure2Vec [32] as a graph embedding framework. Based on the graph topology, Structure2Vec technique aggregates recursively vertex features. Then, the network generates a new embedding of features for every vertex. As shown in Algorithm 1, Structure2Vec based-network starts with an initial embedding at vertex 0 and updates the embedding at every iteration. To obtain the final vector embedding, we took the average of all iterations results. The Structure2Vec process takes two inputs, precisely, an array of nodes' embedding vectors that capture their related properties and adjacency matrix of the program dependence graph, which gives information about the graph's topology, mainly, nodes' connections. In a nutshell, Structure2Vec process is executed as follows: ) return v f Algorithm 1: PROGRAM Dependence Graph Embedding 5) Structure-based Neural Network: After the graph embedding phase, we designed a Multi-Layer Perceptron (MLP), which is a neural network with nodes as neurons with logistic activation. Our aim is to identify whether an application is benign or malicious. Thus, our detection approach is a binary classification process. Accordingly, we designed our neural network to have 64 input neurons, which is equal to the embedding size of an application's program dependence graph. As for the output, we select 2 neurons, one for the benign class, whereas the other for the malware class. Regarding the number of hidden layers, although these layers are not directly interacted with the external environment, we selected 2 hidden layers to tremendously impact the final output. In a nutshell, our neural network can be expressed as the following formula: W 1 and W 2 , represent by wi 1 , wi 2 ∈ R p , the weights of two hidden layers of our neural network. bi 1 , bi 2 ∈ R p are the offsets from the origin of the vector space. In this setting, based on the activation function's output, a program dependence graph G h can be classified as malicious if f (G h ) > 0 or benign if f (G h ) < 0.

B. Native-code based Malware Detection
Nowadays, several Android malware detectors make use of static analysis techniques. They operate only at the bytecode level, which enables malicious payloads embedded in native code to go invisible as a type of obfuscation technique. As a result, to achieve complete analysis of Android applications, we need a second subsystem that operates on the native code level. In this section, we discuss the structural native-code malware detection subsystem which deals with the native code of Android applications. As illustrated in Figure 1, our second subsystem is a four-step process. 1) FCG Extraction: As a first step, we disassembled Android applications and extracted function call graph based on Angr [38], a python framework for analyzing binaries.
2) Function Embedding: As a second step, to catch the function call graph topology, we need to consider each function as a node. Normally, a function can involve one or more basic blocks. Each basic block can contain one or more Dalvik instructions. Therefore, our target is to consider every instruction in a function. To this end, we utilized the SIF [39] network to compute the function embedding by using the sequence of instructions vectors generated by the Word2Vec method.
Input: Instruction embedding v i : i ∈ I, a set of instructions, parameter α and estimated probabilities p(i) : i ∈ I of the instruction. Output: Form a matrix X whose columns are v f : f ∈ F , and let v be its singular vector Based on natural language processing (NLP), given the discourse vector c f , the probability of an instruction which is emitted from the function f is modeled by, wherec f = βc 0 + (1 − β)c f , c 0 ⊥ c f , where α and β are scalar hyperparameters, and Zc f = i∈f exp(<c f , v i >) is the normalizing constant.
The function embedding will be defined as the max likelihood estimate for the vector c f that generated it. By the model (3), the likehood for the function is (4) Let denote the log likelihood of function f as follows: After gradient computation and Taylor expansion, we get the maximum likelihood estimator forc f on the unit sphere is: That is the max likelihood estimate is a weighted average of the vectors of the instructions in one function. To estimate c f , we computed the first principal component of c f for a set of functions as the direction of c 0 . We present our simple function embedding method in Algorithm 2.
3) Function Call Graph Embedding: After getting every function's vector, we converted the graph's nodes and edges into vector space to feed our neural network-based classifier. To this end, similarly to program dependence graph embedding, we used Structure2Vec as an embedding framework. Algorithm 1 describes our function call graph embedding. 4) Native Code Malware detection: After the graph embedding step, we designed our multi-layer perceptron (MLP). Similarly to structural malware detection, our approach is a binary classification process. Thus, in our work, we followed the JN-SAF [40] methodology and label all the native libraries included in the following malware families (Boqx, Droidkungfu, Gumen, Lotoor, Ogel, Slembunk, Updtkiller, and Vikinghorde) as malware. For benign samples, we use all labeled native libraries like the JN-SAF [40].

C. Ensemble mechanism
After getting the outputs of two multi-layer perception(MLP), we have designed an ensemble algorithm to combine the two MLP's results during the training and testing step. The weight of two MLP are trained at the training step.

V. EVALUATION
In this section, we evaluate the performance of our layered Android malware detection approach. We apply and check our proposed model against two public malware datasets, namely DREBIN [13] and AMD [41], and one self-collected malware dataset based on VirusTotal [42] API. As for the benign samples, we used AndroZoo [43].   [41]. • AndroZoo-Malware: Besides aforementioned malware datasets to evaluate the classification issue, we also consider AndroZoo as malware source in order to solve the biased datasets issues (mentioned by TESSERACT [44]), both from the temporal and spatial biases. Following the guideline of TESSERACT, we select malware and spatial biases. Following the guideline of TESSERACT, we select malware and benign samples ratio with 10% and 90% (to solve spatial bias), both for the training and testing. In addition, we select our samples from 2017.12.30 to 2019.12.30 (to solve temporal bias). Additionally, we also use VirusTotal to prepare our dataset. But we set our threshold as follows: p 2 = 0 for benign and p ≥ 4 for malware. In total, we find out 5,000 malware samples. • AndroZoo-Benign: A huge collection of Android application gathered from various sources. It involves more than 10 millions applications [43]. We used VirusTotal [42] to scan applications with over 70 antivirus scanners. Additionally, we used a threshold of 4 scanners to label samples. That is, if more than 4 scanners mark an application as malware, we labeled it a malicious. Otherwise, it is considered benign. Our scanning process resulted in 65,000 benign applications. All in all, our dataset can be summarized as Table I, which includes 35,110 malware and 65,000 benign samples.

B. Structural-based Classifier Evaluation
In our structural classifier, we evaluated our malware detection system with the following parameters. We set our batch size to 1. This means, we have trained and tested our classifier with only one program dependence graph in each step. Also, we set our epochs to 30 to achieve optimal training. Further, the used datasets were randomly split into 70% training and 30% testing. In the same manner, as the first layer, we concentrated on the accuracy, precision, recall, F1. As shown in Table II, our testing experiments yield an accuracy of more than 99% on both datasets. This indicates the efficiency of the vectorial representation of the program dependence graph on identifying the structural malicious patterns in an application. Meanwhile, other metrics, such as recall, F1 are also producing significant results. Figure 2 presents the ROC characteristic of our structural-based classifier.
We can see from the Table II that the results for the Ensemble is same with Byte-code based method. The reason is that we did not find any benign applications(byte-code) which hides their malicious behaviors into the native code, but the byte-code level act as benign(this result is same with the [45]) . At the same time, we also find that most applications which act as malware at native code, have multiple native code libraries, but only one or two of them act malicious behaviors. Taking into account that no previous related work has been done on the Drebin dataset, we extracted native libraries from the AMD dataset only. As a result, we obtained 16,387 .so files including seven different architectures namely ARM64, ARM32v7, MIPS, MIPS-r2, X86, X64. Further, all the native libraries that belong to the following families: Boqx, Droidkungfu, Gumen, Lotoor, Ogel, Slembunk, Updtkiller, and Vikinghorde, are considered as malicious native libraries. Moreover, 1,191 of native libraries has ARM architecture. The rest of the architectures has been skipped, as they involve a small number of native libraries. In this experiment, we split our dataset into 70%training data and 30% testing data.
As shown in Table II, Our second classifier achieves an accuracy of 96.6%. Compared to the structural layer, the performance has dropped. This could be linked to the used dataset's size, as we could not get enough information from previous related works.
To contrast with our method, we get 96.6% AUC with the Drebin method and 89.85% with Droidmat on our mixed dataset. Additionally, Adagio gets a lower AUC value, around 87.39%. 3

C. Features Processing and Training Overhead
All work was done on Euklid, a SUSE Linux server with 128Gb RAM's size. Table III illustrates the training time of both structural and inter-language classifiers. We can see that our inter-language MLP is trained much faster than our structural MLP. Regarding features processing, taking a look at Table III, it is seen that FCG extraction is nearly three times faster than the PDG's construction. This is related to the number of nodes a graph may involve. A PDG may contain more than 60,000 nodes, which requires a large amount of hardware and time.

D. Robustness of Structural-Based Approach
With the fruits of neural networks are unquestionable, recent researches have demonstrated that they fail to exhibit robustness against adversarial inputs. Adversarial samples are usually generated from tweaking the regular inputs through small and calculated perturbations to prompt the model to intentionally output wrong classifications.
1) Crafting Adversarial Malware Inputs: In Android malware detection, the aim of adversarial inputs is to cause the classifier to change its output based on the attackers' goals. Further, our structural-based approach depends on feeding the neural network with an application's program dependence graph embedding. Hence, our primary target is to craft malicious embedding vectors to dupe the model into misclassifying inputs. Generally, when it comes to crafting a malicious graph, there exist several techniques to construct adversarial samples, namely, N-strongest nodes [46] which is based on selecting and injecting nodes with biggest impacts on the adjacent nodes till the misclassification is achieved. Another commonly used technique is Random Node Injection [46], this latter is based on the random injection of nodes into a graph. In our work, to obtain crafted malicious inputs, we used the Gradient-based approach.
2) Gradient-Based Approach: Our adversarial attack focuses on increasing the misclassification rate. As mentioned in the previous sections, we feed the structural-based neural network with the program dependence graph embedding, which is represented as a numeric vector that can be manipulated to obtain the desired output. To this end, our work involves calculating the gradient as well as adding the appropriate perturbations, which results in a 4 steps process: 1) We calculated the gradient through the following loss expression: where X is the program dependence graph embedding vector, W 1 and W 2 are the network weights, B 1 and B 2 are the network offsets, and Y is the label. In a neural network, the gradient is usually used as an optimization algorithm to minimize the cost with respect to weights for better adjustments. Since our objective is to craft malicious malware samples, we need to construct embedding vectors such that the loss is maximized. In this case, instead of weights, we calculated the gradient by taking the partial derivative of the loss function with respect to X, which is the program dependence graph embedding vector.
2) We took the gradient sign to know which way to follow to maximize the loss, either by increasing or decreasing the embedding vector. 3) In this step, we multiplied the gradient sign by epsilon , which is a small value constant to make sure that our    3) Model Robustness Evaluation: With our neural network has yielded high accuracy on the used datasets, their accuracy drops slightly in the presence of adversarial perturbations to test samples. As shown in Figure ??, as the test set grows in size, the accuracy on the adversarial inputs moves closer to the accuracy achieved on normal test samples. Our experiment involves 4 testing stages, each with different dataset sizes. We selected 100, 500, 1000 and 2000 as size metrics to show the difference in the accuracy's behavior on both normal and adversarial samples. With 100 samples, the accuracy drops by nearly 17% Next, the accuracy rate increases proportionally to the size of the dataset. At stage 4, with 2000 samples as a test set, for both datasets, the drop rate has reached 1%, which proves that our neural network is robust against the crafted adversarial samples.

VI. RELATED WORKS
Over the recent years, the detection of Android malware has been under the spotlight of security researchers. Besides the traditional methods such as signature-based and code matching methods, a huge amount of work has been invested into proposing various Android malware detection using machine learning techniques. In the following, we first discuss related works on the structural detection of Android malware using graphs. Next, we proceed to present techniques specifically related to inter-language analysis of Android applications.

A. Android Malware Detection
Drebin [13] presents a broad static analysis to detect the Android malware. It evaluates 123,453 applications and 5,560 malware samples. Drebin detects 94% of the malware with few false alarms and requires 10 seconds for an analysis on average.
In-the-lab and In-the-wild validation [47] presents several machine learning classifier that only on a set of features build from applications' CFGs. It shows that in the lab the performance outperforms existing machine learing-based approaches. Meanwhile, in the wild scenarios the performance gap, especially F-measure dropping from over 0.9 in the lab to below 0.1.
Mamadroid [48] presents an Android malware detection system that relies on app behavior. It builds a behavior model, in the form of a Markov chain, from the sequence of abstracted API calls performed by an app, and uses it to extract features and perform classification. By evaluating on a dataset of 8.5 K benign and 35.5K malicious apps, Mamadroid shows that it not only effectively detects malware(with up to 99% F-malware), but also that the model built by the system keeps its detection capabilities for long periods of time (on average, 86% and 75% F-measure, respectively, one and two years after training).
CWLK [12] presents a method to enrich the feature space of a graph kernel that inherently captures structural information with contextual information.It applies the feature-enrichment idea on a state-of-the-art graph kernel, namely, Weisfeiler-Lehman Kernel(WLK) to obtain the Contextual Weisfeiler-Lehman Kernel(CWLK). CWLK evaluates with more than 50,000 Android apps, and outperforms two graph-kernels and three malware detection techniques by more than 5.27% and 4.87% F-measure, respectively, while maintaining high efficiency.
CDGDroid [11] uses the semantics graph representations, that is, control flow graph(CFG), data flow graph(DFG), and their possible combinations, as the features to characterise Android applications. It encodes the graphs in to matrics, and use them to train the classification model via Convolutional Neural Network(CNN). In more detail, given a CFG(or DFG) g, CDGDroid encodes it into a matrix A with size 222*222(total opcodes number in the Android Dalvik-bytecode list) as follows: for each edge (n1,n2) ∈ g.E, CDGDroid add the element A[op(n 1 )][op(n 2 )] by 1, where A is initialized as a zero matrix with size 222*222 and op(n) returns the opcode of the node n.

B. Structural Detection of Android Malware
Recently, building an obfuscation-resilient Android malware detection has become an urgent demand. Accordingly, many structural approaches have been proposed to identify malicious patterns via control flow graphs or call graphs. For example, Gascon et al. [10] present a method for malware detection based on efficient embedding of function call graphs with an explicit feature map inspired by a linear-time graph kernel. They conducted experiments on 12,158 malware samples, achieving an accuracy of 89%.
Additionally, Ma et al. [49] present an approach of Android malware classification based on supervised learning on the network properties of control flow graphs. Their evaluation was performed on 10010 benign applications and 10,683 malicious applications, attaining 98.98% detection precision with high accuracy. In our approach, we differentiated ourselves from previous works by employing the PDG which considers the composition of both functions and data entirely. Also, we utilized the graph embedding technique to transform nodes and edges into vector space while preserving their properties. Moreover, the accuracy score of our structure-based neural network was above 99% on both datasets.

C. Inter-language Analysis of Android Malware
With nearly all detection approaches focusing on the Manifest attributes as well as the bytecode level of Android applications, malware authors employ various obfuscations techniques on the native code level to create malware variants. In other words, the native code has become a potential threat vector that can go overlooked by existing detection systems. Consequently, Several methods have been proposed to operate on the interlanguage side of Android applications. For example, Alam et al. [50] present DroidNative, an Android malware detector that operates on both native and bytecode level by using specific control flow patterns to reduce the effect of obfuscations and provides automation. Additionally, Wei et al. [51] present a new approach to conduct inter-language dataflow analysis of Android apps and build an analysis framework, called JN-SAF to compute flow and context-sensitive inter-language points-to information in an efficient way.

VII. LIMITATIONS
Any Android malware detection work is immensely proportional to the quality and quantity of the used dataset. In our work, with the process of collecting benign samples is direct, gathering sophisticated Android malware is a demanding task that entails technical efforts. Apart from that, the main limitation of our layered approach is the training phase of our structural layer which employs graph embedding. As we use program dependence graph, the majority of the extracted graphs have a huge amount of nodes which demand a largesize main memory (RAM). Unfortunately, with a RAM of 128 Gb, the process of extracting a graph with more than 90,000 nodes gets killed. Consequently, we disregarded any graph with more than 90,000 total of nodes. Moreover, in terms of robustness evaluation, we had no adequate time to largely assess the robustness of the inter-language layer using adversarial attacks.
VIII. CONCLUSION AND FUTURE WORK In this paper, we presented an approach that employs the principle of detection in depth. To be specific, our method blends two detection techniques that handle different aspects of an Android application. Our structure-based layer focuses on the structural side of an Android application, specifically the code's properties and their relationships, whereas the interlanguage layer acts on the native code level. Further, the use of graph embedding technique is shown to be efficient, as it led us to achieve high performance. As far as we know, this is a first work to combine both byte-code (DEX file) and nativecode (SO file) in Android malware detection. Hence, adapting this technique to other areas, such as desktop malware and phishing detection seems to be an interesting avenue for future research.


Bristle: Decentralized Federated Learning in Byzantine, Non-i.i.d. Environments

Federated learning (FL) is a privacy-friendly type of machine learning where devices locally train a model on their private data and typically communicate model updates with a server. In decentralized FL (DFL), peers communicate model updates with each other instead. However, DFL is challenging since (1) the training data possessed by different peers is often non-i.i.d. (i.e., distributed differently between the peers) and (2) malicious, or Byzantine, attackers can share arbitrary model updates with other peers to subvert the training process. We address these two challenges and present Bristle, middleware between the learning application and the decentralized network layer. Bristle leverages transfer learning to predetermine and freeze the non-output layers of a neural network, significantly speeding up model training and lowering communication costs. To securely update the output layer with model updates from other peers, we design a fast distance-based prioritizer and a novel performance-based integrator. Their combined effect results in high resilience to Byzantine attackers and the ability to handle non-i.i.d. classes. We empirically show that Bristle converges to a consistent 95% accuracy in Byzantine environments, outperforming all evaluated baselines. In non-Byzantine environments, Bristle requires 83% fewer iterations to achieve 90% accuracy compared to state-of-the-art methods. We show that when the training classes are non-i.i.d., Bristle significantly outperforms the accuracy of the most Byzantine-resilient baselines by 2.3x while reducing communication costs by 90%.

Introduction
Machine learning applications have gained significant traction and are widely used for various purposes, such as understanding consumer preferences [10], recognizing pictures [42], predicting keystrokes [14], or translating texts [17]. Traditionally, these applications use neural networks trained on a single server using a tremendous amount of data generated by a large number of geo-distributed, heterogeneous edge devices such as smartphones, IoT devices, or autonomous vehicles [35]. However, centralized training on data streams generated by such devices is limited by the following three factors. First, transmitting training data over the Internet can pose a significant burden on backbone networks. This burden is particularly problematic when media such as photos or videos are used as training data and is worsened by the fact that most learning applications communicate with cloud providers over wireless links [46,78]. Second, maintaining a central server architecture can quickly become expensive and time-consuming as the number of devices increases [24]. Third, transmitting personal and sensitive information over the Internet, such as text conversations or photos, to cloud providers raises privacy concerns and is in certain jurisdictions not even allowed by regulations such as the US HIPAA [28] and the European GDPR law [75].
Federated Learning (FL) overcomes these three limitations. With FL, edge devices do not send their data to the server training the model but instead communicate model updates to a so-called parameter server, also see the left side of Figure 1 [15]. The parameter server coordinates the learning process by pushing model updates to devices (step 1 ), and peers train the model with their private data on-device (step 2 ). Then they send the updated model back to the parameter server (step 3 ), after which the server aggregates the incoming model updates into a global model (step 4 ). FL sidesteps the need for the data to leave the device, improving privacy, lowering the computational burden for the server, and decreasing the communication overhead when the model update is smaller than the data to be transmitted per iteration. FL is nowadays used for various applications, including nextword prediction on keyboards [2, 11,13,32], speech recognition [64], wireless communications [12,59], human activity recognition [66], and health applications [9,54,61,63].
The centralized architecture shown in Figure 1 is typical for FL systems. However, even though the parameter server synchronizes the learning process between remote edge devices, this approach comes with significant drawbacks [7,51,84]. Notably, the parameter server not only poses a single point of failure susceptible to crashes or hacks, but it may also become a performance bottleneck as the number of devices pushing model updates increases [51]. These issues motivate further research to remove dependency on the parameter server and train models in a decentralized manner [22,44,51,73]. With decentralized federated learning (DFL), each peer is connected to a subset of the other peers in the network from which it receives incoming models and to which it pushes its updated models [58]. We visualize this approach on the right side of Figure 1. DFL has resulted in a new wave of learning methods that achieve comparable model accuracy as state-of-the-art FL approaches [34] while boasting several significant advantages. First, decentralized networks are fault-tolerant by design since peers continuously update their knowledge about which other peers are online or stopped communicating [76]. Second, decentralized networks are self-scaling. When a new peer joins the network, other peers can start communicating with the newly-joined peer seamlessly. Because there is usually a maximum number of other peers with which each peer communicates, the connection ratio will drop, but the network will typically still be strongly connected [27]. Third, DFL unlocks AI with zero-cost infrastructure (from the developer's perspective) since the computational power needed to train the network is delivered by all peers in the network working together instead of a parameter server under centralized control [25].
Limitations of DFL. Despite the benefits of DFL, we identify three challenges that reduce its potential for practical applications. The first barrier is that both existing FL and DFL architectures have to consider Byzantine attacks, the situation where malicious peers aim to undermine the model's training by purposefully sending specific model updates to the parameter server or other peers [90]. Since malicious peers keep their data private, they can easily "poison" their model and disseminate this malicious model without repercussions. Byzantine attacks are often addressed by the Gradient Aggregation Rule (GAR), which aggregates and combines incoming model updates [6,56,90]. At the same time, stateof-the-art GARs typically assume that the majority of peers act honestly, which is hard to guarantee in networks with open participation [88].
The second challenge is that the performance of conventional FL systems degrades significantly when being deployed in an environment where the distribution of the training data differs between peers. This is also known as non-i.i.d.
(not independent and identically distributed) data. Given that data is typically non-i.i.d. in an FL environment [6,14,90], dealing with non-i.i.d. data is considered a key challenge in FL [38]. The inability of most GARs to handle non-i.i.d. data results in Catastrophic Forgetting, a phenomenon where the peers overwrite model parameters that were important to predict a particular class distribution with parameters essential to predict another class distribution [91].
The third challenge relates to the communication requirements to disseminate model updates among peers in the network. In DFL, each peer disseminates a copy of the current model at every training iteration to several other peers. However, modern neural networks may consist of millions of parameters [33,36], sometimes requiring gigabytes of data to be transferred for each model exchange. Facilitating this amount of data quickly becomes infeasible when the number of devices and the frequency of model updates increase [62].
Although some DFL systems are to a certain extent Byzantineresilient [6,31,56,85], able to deal with non-i.i.d. data [15,65,93], or focus on reducing the communication costs [3,21,80], there exists -to the best of the author's knowledge -no DFL solution that addresses all three challenges simultaneously. We argue that such a solution is a key requirement for a wide deployment of DFL systems.
Our Contributions. To the best of the author's knowledge [31,85,86,94], only four papers have ever been published about DFL that are Byzantine-resilient (first challenge), none of which are suitable for situations where the data is non-i.i.d. (second challenge) or decrease the communication requirements (third challenge). Therefore, we present Bristle: the first Byzantine-resilient and communication-efficient approach for DFL in environments with non-i.i.d. classes. 1 Bristle is a pure edge solution and acts as a middleware between the machine learning application and the decentralized network layer by combining three techniques: Similar to related work in the FL domain, Bristle focuses on supervised learning problems that train a neural network for classification [55,56,81]. We implement all elements of Bristle as an Android library and open-source our implementation (see Section 3.4).
With an extensive set of experiments with the popular MNIST dataset, we evaluate the performance and resilience of Bristle. We compare Bristle with five related approaches for FL and quantify the Byzantine-resilience of these approaches under four attacks in the domain of FL, aimed at reducing the model's accuracy. The experiments show that even in highly Byzantine environments where the classes are non-i.i.d., Bristle not only withstands all evaluated attacks but also outperforms all related approaches in terms of convergence speed, accuracy, consistency, and communication efficiency. We highlight one of the key results from our experiments in Figure 2, showing model accuracy as peers train the model. In this figure, the performance of Bristle and evaluated DFL approaches is illustrated in a Byzantine (40% of the peers perform a label-flip attack) and non-i.i.d. environment (the class overlap between the peers is just 40%). Despite this challenging environment, Bristle quickly converges and outperforms all other approaches in terms of accuracy while reducing communication costs by over 90%.

System and Threat model
We now describe our system and threat model, and state the assumptions underlying our work.
Network Model. We consider an unstructured, strongly connected peer-to-peer network with peers. Each peer knows the network addresses of other peers in the network. We assume unreliable and unordered network channels between peers. In addition, we do not place any restriction on peers joining the system, and peers can join or leave the system at any time. We consider the mitigation of attacks targeted at the network layer, e.g., the Eclipse Attack, beyond the scope of this work.
Training Data. Each participating peer acts on local training dataset which size is denoted by | |. Training data never leaves the device, and is only known to peer . In contrast to most related work, we assume that the number of samples per class is not distributed uniformly among peers (non-i.i.d), which is a key characteristic of FL environments [6,14,90]. However, we also assume that for each class the samples are distributed uniformly (i.i.d.) between peers as a prerequisite for the performance-based integrator (see Section 3.3).
Model Training. Our approach focuses on supervised classification problems where the dataset consists of a collection of input-output pairs. The input is a chunk of data with a fixed size, and the output is a qualitative label associated with a class. The devices aim to minimize the loss function by tuning the parameters in the neural network such that its predictive capabilities are maximized. We use the negative log-likelihood of the ground truth class as the loss function. Since this problem is intractable for complex models, we use, in line with most literature [47,70,71,90], a technique called Gradient Descent (GD) which iteratively takes the derivative of the loss function with respect to the training data and then moves the hyperparameters in the direction of the gradient. However, because the local dataset can be large, it can take a long time for GD to converge [8]. Therefore, we use the faster Stochastic Gradient Descent (SGD), where a subset (mini-batch) of five samples is stochastically sampled from the dataset to update the parameters in a particular iteration.
Threat Model. Our work assumes an environment with an unconstrained number of Byzantine attackers aiming to subvert the model's performance. This includes the Sybil Attack, an attack where a malicious peer joins the network under many different identities to prevent model convergence [23]. It also includes collusion, the situation where malicious peers in concert attempt to undermine model convergence. Byzantine attackers can send arbitrary model updates to any peer in the network, but have no access to the private samples of benign peers.

Bristle: Middleware for Decentralized Federated Learning
Bristle enables DFL that can handle non-i.i.d. classes and thwart Byzantine attacks while improving communication costs compared to existing approaches. We provide a highlevel overview of Bristle and the actions performed during a training iteration in Figure 3. First, Bristle takes advantage of deep transfer learning to determine the non-output layers of each node before the first training iteration (step 1 ). As we will experimentally demonstrate in Section 5, this  significantly reduces communication costs compared to communicating the entire model, speeds up the model convergence rate, and acts as a prerequisite to learning on non-i.i.d. classes.
The main innovation of Bristle is its two-phased GAR that integrates received models. During each training iteration, a peer trains the local model on a mini-batch of their private dataset and only updates the output layers (step 2 ). It then forwards the updated output layer 2 and the output layers it has received from other peers to a distance-based prioritizer (step 3 ). This fast distance-based prioritizer estimates the best candidates for integration based on an exploreexploit ratio and forwards them to the performance-based integrator (step 4 ). The performance-based integration is more computationally demanding and integrates the prioritized output layers into the peer's current output layer. This integration process is both Byzantine-resilient and capable of continual learning, facilitated by selective updating of the output layer, per-class performance evaluations, and a carefully crafted weighted averaging function. Our main motivation to use a two-staged approach is that a distancebased prioritizer on itself is ineffective and performancebased integration on all received models is too computationally expensive since it requires the evaluation of incoming models on private data. Finally, Bristle transmits the output layer to a few connected peers (step 5 ) and uses the new output layer as input for the next training iteration (step 6 ). In the remainder of this section, we elaborate on the model pre-training, the distance-based prioritizer, and the performance-based integrator.

Bootstrapping Bristle with Transfer Learning
In conventional FL settings, the parameters of the entire neural network are shared with the parameter server or, when using DFL, with other peers. These parameters include all weights and biases of the input layer, hidden layers, and the 2 We use the terms output layer and model interchangeably in this work. output layer. In Bristle, we avoid exchanging the full neural network between peers. Instead, we leverage a popular ML technique called deep transfer learning which re-uses a neural network that has been trained on another dataset with comparable low-level features as the training data (step 1 in Figure 3) [72]. More specifically, we copy and subsequently freeze the non-output layers from another model. Bristle then only trains and exchanges the output layer, which has three major advantages: 1. Copying the non-output layers from a well-trained model significantly improves the convergence rate when training the model in a decentralized fashion on devices with lower hardware capabilities. 2. Freezing non-output layers reduces communication overhead since only the output layers have to be shared among peers. 3. Freezing the non-output layers is a key step towards continual learning, which further increases the performance and robustness of Bristle (see Section 3.3).
To bootstrap Bristle with a pre-trained model, we must assume that for the dataset we want to train on, there exists a vastly bigger dataset with roughly the same low-level features that we can use to pre-train a similar model. Considering the extent to which transfer learning is nowadays used in practical learning problems, we argue that this assumption is realistic and does not prohibitively degrade the applicability of Bristle [1,60]. The training of the initial neural network can be performed offline by system designers or volunteers. The pre-trained model can then be shared with peers by bundling them in the (mobile) application or be served by a trusted server that sends interested peers the pre-trained model upon request. We assume that the developer knows the number of classes beforehand to determine the size of the output layer. 0 1 2 Euclidean distance to its own model Figure 4. Average Euclidean distance from a given model to benign (green) and malicious (red) models, and models trained on an entirely different data distribution (orange).

Distance-based prioritizer (DBP)
We now elaborate on the distance-based prioritizer (DBP) in Bristle (step 2 in Figure 3). The inputs to the DBP are the output layers received from other peers during the last training iteration. To explain the motivation behind the DBP, we first examine Figure 4 where the average Euclidean distance is shown from a non-i.i.d. model (configured as explained in Section 5.3) to two benign models (shown in green), a benign model that is trained on an entirely different data distribution (shown in orange), and several Byzantine models (shown in red). The distances in this figure are based on the models exchanged during our experiments (see Section 5). For each distance shown in Figure 4, we took the average distance over 100 runs (with the current and the other model both trained ten times on different training data) and trained all models to convergence before comparing the distances. The figure shows that based on the Euclidean distance alone, we cannot reliably determine if a certain model is benign because, in this example, the distance to a Trimmed Mean attack model is between the distances to two benign models. However, the distance may clearly help prioritizing certain models since models with rather low or high distances appear to be more likely to be malicious.
Based on this insight, we segment the received models into three equally-sized categories with a low, medium, and high distance from our current model. Then, we uniformly sample models from each of these categories. The number of models sampled from each category depends on the explorationexploitation ratio where = 0 exclusively samples lowdistance models (exploitation-dominant) and = 1 exclusively samples high-distance models (exploration-dominant). The optimal value of depends on the maximum distance that benign models can reasonably have to each other, which is highly dependent on the degree of asynchrony (higher asynchrony → higher ), the expected ratio of benign to Byzantine peers (more Byzantine peers → lower ), and the degree of non-i.i.d.-ness (higher non-i.i.d.-ness → higher ). The advantage of using three categories is that in situations where the accuracy is clearly sub-optimal and a significant number of Byzantine attackers are present, the developer may want to emphasize integrating models with a medium distance since these will often perform best. , and ℎ denote the fraction of samples from the low, medium and high distance categories, and are determined as follows: Note that + + ℎ = 1. Figure 5 visualizes the relation between the above values and . We also parameterize the maximum number of models that pass our DBP, denoted by . Since the runtime of our performance-based integrator scales with the input size, devices with lower performance can opt for a lower value for .

Performance-based Integrator (PBI)
The ability of our distance-based prioritizer to recognize Byzantine or stale models that are trained on a lower number of iterations is rather limited. Byzantine attacks are easy to launch in open networks, and stale models are a regular phenomenon in FL systems [49]. To address these concerns, we assess the performance of each model that passes the distance-based prioritizer on a small test dataset (step 4 in Figure 3) using a performance-based integrator (PBI). This test dataset is a random subset of the full private dataset owned by the peer. Figure 6 shows how the PBI works, given a model with three classes ( , and ). In summary, the PBI selectively integrates the parameters of classes that perform well to achieve Byzantine-resilience and to handle non-i.i.d. classes Prioritized output layers My output layer Data  properly. This is different from existing approaches that integrate each received model as a whole instead. We refer to the parameters in the output layer that are connected to a particular class as Class-specific parameters (CSPs). The integration process in Bristle first evaluates the performance of each class of each received model on a test dataset (step 1 ). Based on this evaluation, we compute a certainty score that estimates how benign a received model is (Step 2 ). Then, we calculate for all CSPs of each model a weight (step 3 ). Finally, we integrate the received models into our current model, based on the computed weights (step 4 ).
The selective integration of parameters is inspired by the continual learning algorithm CWR* [52] that enables noni.i.d. learning by initializing the output layer to zero, applying a mean-shift, and replicating the hippocampus-cortex duality by selectively copying and resetting parts of the output layer. Related work demonstrates that this approach provides excellent performance in regular non-FL environments and enables per-class updates [52]. Applying continual learning requires that the non-output layers are frozen and equal between all peers. We already addressed this by using transfer learning (see Section 3.1) to train these layers before the first iteration.
We now elaborate on the PBI logic, which pseudocode is given in Listing 1. The input for this algorithm is the current model of the peer (myModel), and the prioritized models that passed the DBP (prioritizedModels).
Step 1 (per-class performance measurements). Based on a subset of the local dataset, we first calculate the F1-score for the CSPs of all familiar classes of both the peer's own output layer and the prioritized output layers (line [4][5][6][7][8]. We refer to a class as familiar when the peer has a sufficient number of samples, denoted by , to reliably estimate the performance of that class of a given model. This threshold is determined by the developer. With a higher value of , the PBI can more reliably determine F1-scores, but the number of classes for which insufficient samples are available to evaluate, also known as foreign classes, might decrease. We chose to measure F1-scores instead of the accuracy as a proxy for the performance since the former is more suited for imbalanced datasets [16]. The data subset used by the PBI is never used to train the peer's own model since this would result in an overestimation of the performance of the peer's own model. Since these measurements depend on the availability of sufficient private data samples, Bristle avoids integrating models from other peers until sufficient private data samples are available to test them reliably.
Step 2 (certainty computation). Then, we calculate for each prioritized model a certainty score, which is a (rough) estimate of the degree to which this model is benign (line [10][11][12]. This certainty score is determined by subtracting the standard deviation from the average F1-score of the bestperforming familiar classes (line [11][12], thus rewarding high class performance and punishing high variation among the class performance. We do not consider all classes when computing the certainty score since it is not realistic to assume that all classes of each benign received model perform well in a non-i.i.d. environment. The larger is, the more robust the algorithm is against Byzantine attacks, but the less able it is to learn about foreign classes in the case of a non-i.i.d. setting. Step 3 (weight computation). Furthermore, we estimate for each familiar class of each prioritized model if integrating its corresponding CSP improves the model's performance by simply checking if the F1-score of that class of the received model exceeds the respective F1-score of the peer's own model (line 14). We call the extent to which it does the F1discrepancy, and we store this value in a two-dimensional array named disc. If the class-specific F1-score of the model being evaluated exceeds that of our own model, we calculated the F1-discrepancy as in line 15. Otherwise, we set the F1discrepancy to −∞ (line 17). The parameter increases the degree to which high-performing classes are integrated.
The computeFaWg function then computes the weights for the familiar classes for each model, taking the prior computed scores and certainty as input (line 19). This function computes the following Sigmoid function, where is the weight of familiar class , is the F1-discrepancy, and is the certainty of the model being considered: This function assigns a weight of one to equally performing classes and an increasingly higher weight to classes that show excellent performance, dependent on the values of 1 and 2 .
represents the boost for above-average performing models and the bounty for below-average performing models. The bigger this discrepancy, the faster the model can catch up with other better-performing models, but the bigger the impact of a malicious model that performs well on familiar classes and bad on foreign classes. We multiply the outcome of the Sigmoid function by the certainty score calculated earlier because the parameters of a class might be sub-optimal even when it has a perfect F1-score when other classes perform poorly. Figure 7 illustrates how the weight of CSPs is affected by their F1-score on a test dataset, assuming that the peer's current model yields a F1-score of 0.5 on that class and that the calculated certainty is 1.
Determining a weight for the CSPs of the foreign classes is challenging because we cannot directly measure their performance. Instead, we take the sum of the scores of all familiar classes and feed this into the same Sigmoid function as used for the familiar classes (Equation 2), albeit parameterized with separate variables 1 and 2 . This is done by the computeFoWg function (line 21).
is the extent to which foreign classes are integrated into the model. The higher this value, the better the model can be when the peer wants to use the model to classify formerly foreign classes, but also the higher the impact when a potentially malicious model is integrated. If the user is uninterested in achieving high performance on foreign classes, 1 can be set to 0.
Step 4 (model integration). Finally, we replace the CSPs of familiar and foreign classes with the weighted average of all CSPs by using the calculated weights (line 24-25).

Implementation
Bristle is implemented on top of an existing network library that provides support for peer discovery, decentralized overlay creation, and authenticated messaging [67,68]. Since we envision the usage of Bristle mostly in a mobile environment, our middleware is written in the Kotlin programming language (the default language for Android applications). We envision that Bristle runs as a background service on the end-users' devices to periodically receive or transmit models from and to peers when the device is connected to Wi-Fi.  Peers transmit model updates using the UDP protocol and network messages are compressed with Gzip. Model training is facilitated by the DeepLearning4j library (version 1.0.0-beta7) to enjoy compatibility with a wide range of advanced ML algorithms. We have published the Bristle source code and developer documentation in a GitHub repository. 3 Using Bristle. Developers can leverage the Bristle middleware by feeding the peer's current model and all received models into Bristle's GAR after each iteration and subsequently replacing the peer's model with the result. The moment a model is updated can be decided by the developer, for example, model training can take place when the device is charging to minimize the impact on end users. The peers should be able to selectively receive and integrate only models relevant to the current ML application. To this end, Bristle uses the functionality to form communication groups as provided by its network library. Deciding on the variables listed under Section 4 is a key part of machine learning. We recommend the developer to use heuristics, optimize them on a related dataset, or use A/B-testing to find the best values to obtain the desired accuracy on the models.

Experimental Setup
We now describe our experimental setup, datasets, and parameters.
Testbed. All experiments are run on an HPE DL385 Gen10 server. This server is equipped with 128 AMD EPYC 7452 CPUs, has 512 GB of DDR4 memory, and runs Debian 10.
Datasets. In line with related research [55,56,81], we consider an image classification application that applies Convolutional Neural Networks (CNNs) to classify images. We use the popular MNIST [45] dataset, consisting of 60,000 gray-scale training images and 10,000 test images of 28x28 pixels representing handwritten digits. To achieve better performance, we standardize the dataset by applying Z-score normalization such that the features are re-scaled to a normal distribution with = 0 and = 1. We pre-train -until convergence -a neural network with the same configuration on the EMNIST-Letters [18] dataset, which features resemble MNIST, but contains characters instead of digits. We then include the resulting neural network in the Bristle software.
Experiment parameters. We list all default parameters used during our experiments in Table 1. An explorationexploitation ratio of 0.4 slightly prioritizes model with lower distance.
Non-i.d.d. data. To evaluate Bristle with non-i.d.d. data, we first sort the data per class, divide the data into equallysized shards, and then assign to every peer several shards, which is also the approach taken by related work [19,77,79]. We note that the more shards we assign to every peer, the better every peer can recognize and defend against Byzantine attacks (see Section 3.3), but the less non-i.i.d. the classes are. We opt to assign -unless specified otherwise -without loss of generality to every peer four shards which cover 40% of the classes to balance between the ability to learn non-i.i.d. classes and to recognize Byzantine attacks.
Model training. We train the dataset on the same CNN architecture used by McMahan et al. [55], except that we use Leaky ReLu instead of the regular ReLu as the activation function for the hidden layers since the former seems to give slightly better performance (specifically, suffers less from the vanishing gradients problem). The model consists of twice a convolutional layer (kernel size = 5, stride = 1, padding = 0) followed by a max pooling layer (kernel size = 2, stride = 2, padding = 0), and finally the output layer (with 800 hidden nodes). For the output function, we use the softmax function, and as the loss function, we use negative log-likelihood. To train the model, we use the Adam optimizer, parameterized as shown in Table 1. Since these values significantly impact the model's performance, we used a grid search with typically 7-9 values for each parameter and ensured that the optimal values were approximately in the middle. Although the baselines were originally not developed to be used in combination with transfer learning, we decided to use transfer learning for all baselines for all experiments anyway since the performance increase is so significant that otherwise any comparison with Bristle would be meaningless (also see Section 5.1).
Baselines. To compare Bristle with existing methods, we implemented five other GARs commonly used in FL: We initialized Krum and BRIDGE, which are dependent on a-priori knowledge of the number of attackers, with = 4 (the maximum number of attackers) and Mozi with = 0.5 (the ratio of benign to Byzantine peers). Byzantine attacks. We also evaluate Bristle under the following four Byzantine attacks, which are commonly considered in the domain.
1. The Label-flip attack [4] assigns an incorrect label to each input [4,29,74]. We implement this attack by numbering all labels and reassigning each sample with label to label ( + 1) % | |. 2. The Additive noise attack [48] adds some noise to the parameters of outgoing models. When the noise has a larger variance, it can indeed prevent convergence but also makes the noise attack easier to detect [48]. Centering the noise around a value slightly different from 0 allows the attack to prevent convergence despite low variance, but since the mean of benign updates is always centered around 0, this attack can be easily    detected. We consider a variant where each half of the parameters are set to noise centered around a value just below and above 0, respectively. 3. The Krum attack [26] specifically targets the Krum aggregation rule. It is an effective, state-of-the-art attack by iteratively sending attack vectors that will be accepted by Krum whilst inflicting maximum damage to the peer's model. 4. The Trimmed Mean attack [26] targets the trimmed mean GAR (Bridge in our experiments). It determines the gradient direction for each parameter of the model and then creates an attack vector that points exactly in the opposite direction, scaled per parameter depending on the values of the other benign peers.

Experimental Evaluation
We now evaluate the performance of Bristle. Our evaluation answers the following questions:

Performance Gains of Transfer Learning
We first evaluate the performance gains of transfer learning when all peers are honest, and the data is i.i.d. For each experiment, we measure after every 10 iterations the performance of all peers and then take the average accuracy, defined as # # . Figure 8 shows the evolution of model accuracy for the baseline GARs and Bristle, both without transfer learning ( Figure 8a) and with transfer learning (Figure 8b). We note that Bristle requires a pre-trained model and therefore is not included in Figure 8a. Figure 8a shows that the evaluated GARs perform quite similarly, although Mozi has a slower convergence rate since it assigns  lower weights to benign models that have not been trained sufficiently yet to perform well. Transfer learning dramatically improves both the convergence rate and the maximum accuracy after 300 iterations of all GARs, which also supports literature [37]. More specifically, whereas reaching 70% accuracy takes on average 55 iterations with regular training, it takes merely four iterations with transfer learning, a reduction of 93%. Reaching 90% accuracy takes on average 180 iterations with regular learning, whereas it only takes 30 iterations with transfer learning, a reduction of 83%. This reduction in iterations to reach the desired level of model accuracy can significantly reduce the load on the network.

Byzantine Attacks
We now evaluate the Byzantine-resilience of Bristle under different attacks when data is i.i.d. Figure 9 shows the effect of different attacks. Bristle withstands all evaluated Byzantine attacks and quickly achieves high model accuracy. Figure 9a shows that the label-flip attack prevents model convergence when using the FedAvg GAR, but is, despite its relatively small influence on the model's parameters, successfully mitigated by all other GARs. Figure 9b shows that the FedAvg and Median GARs are susceptible to the additive noise attack. The Krum attack, shown in Figure 9c, is clearly very effective against Krum but has only a minor effect on the  convergence rate of the other GARs. The Trimmed Mean attack, see Figure 9d, is relatively ineffective against any Byzantine-resilient GAR. This is because all benign models are very close to each other in this scenario, making it hard for this attack to steer the model in another direction without clearly being an outlier.

Non-i.i.d. Classes
We now consider the scenario where the classes are noni.i.d., see Figure 10. In this experiment, there are 10 peers, each of which has access to two random samples of four consecutive classes. Thus, each peer has access to classes { , ( + 1)%10, ( + 2)%10, ( + 3)%10}. When we compare Figure 10b with Figure 10a, it is clear that Krum and Mozi fail to achieve desired model accuracy with non-i.i.d. classes, and we also observe that Bridge and Median converge significantly slower. FedAvg and Bristle show excellent performance and achieve 90% model accuracy in 65 and 55 iterations, respectively. This is because these methods (eventually) combine the information learned by every peer, while the other methods disregard a part of the received models under the incorrect assumption that those are Byzantine.

Combining Byzantine Attacks and Non-i.i.d. Classes
We now evaluate Bristle and other GARs in an environment containing both Byzantine attackers and where the classes are non-i.i.d. (see Figure 11). We use the label-flip attack in all experiments because this one is effective (see Figure 11a) and very popular in related work [26,57,82]. Except for Bristle, all baselines fare poorly in the Byzantine experiments with non-i.i.d. classes. Specifically, we observe that FedAvg is unable to defend against Byzantine attacks, although it achieves an accuracy of 87% in the first few iterations of the Krum attack (see Figure 11c). Although Bridge performs well in the experiments presented in Section 5.2, it performs poorly under the threat of Byzantine attacks when the classes are non-i.i.d. Krum is, as expected, unable to defend against the Krum attack but performs under the threat of the other attacks roughly on par with Mozi. Mozi shows the same accuracy as in the benign non-i.i.d. experiments (see Figure 9) because it successfully defends against Byzantine attacks but is also maxed out on the poor maximum accuracy that it can attain on the node's own dataset. The performance of the Median baseline varies significantly depending on the attack and may be quite inconsistent (as illustrated in Figure 11b and Figure 11d). An interesting finding is that the Trimmed Mean attack is relatively ineffective in the i.i.d. experiment (see Figure 9d) but impacts the performance of the same baselines significantly in the non-i.i.d. experiment (see Figure 11d). This results from the greater distance between the benign models in the non-i.i.d. experiment, giving the attack more leeway to steer the model in a different direction without being considered an outlier. Since the PBI assigns a weight of  Varying the Number of Byzantine Attackers. We now vary the number of Byzantine attackers, see Figure 12. Figure 12a shows that even with 10% Byzantine attackers, the performance of the baselines already degrades significantly. Bristle manages to maintain a quick increase in accuracy for all considered attack scenarios. With 10% and 30% Byzantine attackers, Mozi manages to keep a stable performance but is limited to predicting only the peer's familiar classes correctly. Figure 12d shows that the performance of Krum is inconsistent and that only Bristle achieves a consistent high performance. Bristle's excellent performance results from the fact that (a) in contrast to Mozi, Bristle evaluates and integrates the parameters per class instead of per model, and (b) in contrast to the other GARs, Bristle uses performance evaluations instead of just distance comparisons.
Varying the Degree of Non-i.i.d.-ness. We now compare the performance of the GARs in three situations where the classes are to a varying extent non-i.i.d. (see Figure 13).
FedAvg and Bridge are, regardless of the degree of non-i.i.d.ness, unable to provide any resilience to the label-flip attack. Mozi defends, similarly to the experiments in Figure 11, perfectly well against the label-flip attack but is limited to the maximum accuracy that can be obtained by training on its own dataset. The performance of Krum increases with the number of classes owned by the peer. The Median rule performs relatively well, even when the classes are highly non-i.i.d. Bristle, however, clearly performs best compared to all baselines, although its performance decreases when the peers have only 20% of the data (see Figure 13a).
Varying the Connection Ratio. In larger networks, it is unrealistic to assume all-to-all dissemination of model updates. To test the impact of the connection rate on the convergence rate more accurately, we set up an environment with 100 peers where the classes are again non-i.i.d. similarly to the previous experiments. We setup two experiments, connect each peer to a random subset of 2% and 5% of the other peers respectively, add an equal number of label-flip attackers that are connected to each benign peer, and measure the average accuracy over time. From Figure 14a, we observe that when the connection rate is only 2%, FedAvg and Median perform very poorly, but also the other GARs are unable to achieve satisfactory accuracy. When the connection rate increases to 5% in Figure 14b, Bristle and Krum perform quite well in contrast to the other baselines. Thus, it seems that in a setting with 100 peers, a connection rate of only 5% is already almost enough to reach the maximum accuracy. The number of iterations required to obtain this accuracy is relatively high compared to a connection rate of 100% (see Figure 11a). relatively inexpensive operations, such as calculating the distance between models and sorting the parameters of each dimension. Mozi is relatively slow because it has to evaluate the accuracy of each model. Bristle is initially by far the slowest GAR caused by the performance-based integrator that evaluates the performance not just for each model but for each familiar class of each model. However, when the number of connected peers exceeds (see Section 3.2), adding more peers has a negligible impact on the speed of Bristle because the distance-based prioritizer is efficient in reducing the number of models to .

Bristle Efficiency and Scalability
All baselines consume an equal amount of network traffic (roughly 3 MB per iteration per peer for our neural network), but because Bristle transmits only the output layer (roughly 300 KB), the bandwidth requirements of Bristle are reduced by 90%.

Related work
In the last five years, a considerable amount of literature has been devoted to creating more effective FL systems. Most work focuses on achieving Byzantine-resilience but also introduces several methods to reduce the bandwidth requirements and to improve learning on non-i.i.d. classes.
Byzantine-resilience. Several well-known Byzantineresilient GARs are Coordinate-wise Median (CM) [57] which takes the median across all models for each parameter, Krum [6] which selects the model that most closely resembles all other models, and Bulyan [56] which iteratively applies Krum followed by a variant of CM. However, these GARs use distances as a proxy for benignness, which it not reliable as we have seen in Section 3.2. In contrast, performance-based methods reject or accept received models based on their performance on a test dataset. Examples include RONI (Reject On Negative Influence) [5] which simply discards all models with a negative impact on the model, and Zeno [82] / Zeno++ [83] which use a central oracle to estimate the true gradient and only keep the gradients most similar to this estimation. Bristle uses distances only to prioritize the received models and uses per-class performance measurements to integrate models.
Communication efficiency. Because of the bandwidth limitations of cellular networks, numerous methods were proposed to improve the communication efficiency of FL. A popular method is to quantize the gradients to low-precision values [3,21,80] or only to transmit the most important parameters (sparse matrix methods) [40,69]. Bristle only updates the output layer, which works well together with existing techniques to reduce the communication overhead.
Non-i.i.d. learning. Several methods enable learning on non-i.i.d. classes, such as by sharing a small i.i.d. training dataset across all peers [93] or by reusing non-federated continual learning techniques [30,41,43,89]. Bristle also lends several concepts from a non-federated continual learning technique, namely CWR* [53] (see Section 3.3).
FL systems. Several FL systems try to combine Byzantineresilience with learning on non-i.i.d. data. RSA [47] uses a regularization-based strategy and although it performs relatively well when the data is non-i.i.d., it fares poorly against Byzantine attackers. FoolsGold [29] detects and rejects attacks executed by multiple sybils working together and works well with non-i.i.d. data. However, Zhao et al. [92] show that the Byzantine-resilience of FoolsGold is quite limited. FLeet [20] uses past observed staleness values and similarities with past learning tasks to achieve learning on non-i.i.d. data for a specific type of "soft" Byzantine attacks (namely the presence of stale models) but is unsuitable for other types.

Concluding Remarks
We have presented Bristle, middleware for decentralized, federated learning that tolerates Byzantine attacks, even when the classes of the training data are non-i.i.d. By leveraging deep transfer learning, Bristle achieves a high convergence rate despite having a low communication overhead. Through the combination of a fast distance-based prioritizer and a per-class performance integrator, Bristle is able to withstand attacks targeted at subverting the model accuracy. Our experimental evaluation using the popular MNIST dataset has demonstrated these desirable properties and shows that Bristle exhibits superior performance compared to related solutions. In this evaluation, we did not focus on privacy, communication compression, or other aspects that are supplementary to Bristle and addressed in the existing literature. We have implemented and open-sourced Bristle on GitHub.
Although we believe that Bristle is a significant step forward for DFL, we identify two directions for further work. First, communication costs could be further reduced by selectively sending parameters to peers with high class overlap. This can be estimated using Private Set Intersection Cardinality (PSI-CA). One can prevent peers from learning too much about the class distribution of others, e.g., by adding noise to the cardinality and by rate-limiting PSI-CA requests. Second, the accuracy could be increased even more when the non-output layers can also be fine-tuned rather than being fixed. Several popular continual learning algorithms are suitable for this purpose, such as LWF [50], AR1 [53], or EWC [39]. However, tuning also the non-output layers requires the transmission of information about these non-output layers, significantly increasing the communication costs. Additionally, it is non-trivial to maintain the Byzantine-resilience property because the parameters in the hidden layers do not correspond directly with the classes to be predicted.