Vulnerability Analysis of 2500 Docker Hub Images

The use of container technology has skyrocketed during the last few years, with Docker as the leading container platform. Docker's online repository for publicly available container images, called Docker Hub, hosts over 3.5 million images at the time of writing, making it the world's largest community of container images. We perform an extensive vulnerability analysis of 2500 Docker images. It is of particular interest to perform this type of analysis because the vulnerability landscape is a rapidly changing category, the vulnerability scanners are constantly developed and updated, new vulnerabilities are discovered, and the volume of images on Docker Hub is increasing every day. Our main findings reveal that (1) the number of newly introduced vulnerabilities on Docker Hub is rapidly increasing; (2) certified images are the most vulnerable; (3) official images are the least vulnerable; (4) there is no correlation between the number of vulnerabilities and image features (i.e., number of pulls, number of stars, and days since the last update); (5) the most severe vulnerabilities originate from two of the most popular scripting languages, JavaScript and Python; and (6) Python 2.x packages and jackson-databind packages contain the highest number of severe vulnerabilities. We perceive our study as the most extensive vulnerability analysis published in the open literature in the last couple of years.

Introduction
Container technology has been known for a long time in Linux systems through Linux Containers (LXC), but it was not commonly used until a decade ago. The introduction of Docker in [1] made the popularity of containerization rise exponentially. Container technology has revolutionized how software is developed and is seen as a paradigm shift. More concretely, containerization is considered as a beneficial technique for Continuous Integration/Continuous Delivery (CI/CD) pipelines; it is providing an effective way of organizing microservices; it is making it easy to move an application between different environments; and in general, it is simplifying the whole system development life cycle.
Software containers got its name from the shipping industry since the concepts are fundamentally the same. A software container is code wrapped up with all its dependencies so that the code can run reliably and seamlessly in any computer environment isolated from other processes. Hence, containers are convenient, lightweight, and fast technology to achieve isolation, portability, and scalability.
Container technology is replacing virtual machines continuously, and the trend is that more companies are choosing to containerize their applications. Gartner predicts that more than 70% of global companies will have more than two containerized applications in production by 2023. This is an increase from less than 20% in 2019. 1 With the advent of 5G communication technology, it seems that container technology and particularly Docker is finding new venue for application in the domain of network slicing, network management, orchestration and in 5G testbeds [2].
Docker provides a popular registry service for the sharing of Docker images, called Docker Hub. 2 It currently hosts over 3.5 million container images, and the number keeps growing. Images could be uploaded and maintained by anyone, which creates an innovative environment for anyone to contribute and participate. However, on the downside, this makes it hard for Docker to ensure that packages and applications are up to date to avoid outdated and vulnerable software.
When looking at the security of Docker, two aspects need to be considered: the security of the Docker software at the host, and the security of the Docker containers. Docker Inc. claims that "Docker containers are, by default, quite secure; especially if you run your processes as non-privileged users inside the container." [3]. However, it is a simple fact that Docker (the Docker daemon and container processes) runs with root privileges by default, which exposes a huge attack surface [4]. A single vulnerable container is enough for an adversary to achieve privilege escalation. Hence, the security of the whole Docker ecosystem is highly related to the vulnerability landscape in Docker images.
Related work. One of the first to explore the vulnerability landscape of Docker Hub was BanyanOps [5]. In 2015, they published a technical report revealing that 36% of official images on Docker Hub contained high priority vulnerabilities [5]. Further, they discovered that this number increases to 40% when community images (or general images as they call it in the report) are analyzed. BanyanOps built their own vulnerability scanner based on Common Vulnerabilities and Exposures (CVE)scores, and analyzed all official images (≈75 repositories with ≈960 unique images) and some randomly chosen community images. However, at that time, Docker Hub consisted of just ≈95,000 images.
In 2017, Shu et al. conducted a new vulnerability analysis of Docker Hub images [6]. With the aim of revealing the Docker Hub vulnerability landscape, they created their own analysis framework called DIVA (Docker image vulnerability analysis). The DIVA framework discovers, downloads, and analyses official and community images. It is based on the Clair scanner and uses random search strings to discover images on Docker Hub. The analysis revealed that, on average, an image (official and community) contains more than 180 vulnerabilities. They also found that many images had not been updated for hundreds of days, which is problematic from a security point of view. Further, it was observed that vulnerabilities propagate from parent to child images.
To our knowledge, the most recent vulnerability analysis of Docker Hub images was performed during spring 2019 by Socchi and Luu [7]. They investigated whether the security measures introduced by Docker Inc. (more precisely, the introduction of verified and certified image types) improved the security of Docker Hub. In addition, they inspected the distribution of vulnerabilities across repository types and whether vulnerabilities still are inherited from parent to child image. They implemented their own analyzing software using the Clair scanner, and used the results from Shu et al. [6] from 2017 as a comparison. The data set they successfully analyzed consisted of 757 images in total. Of these, 128 were official, 500 were community, 98 were verified, and 31 were certified. They only analyzed the most recent images in each repository and skipped all Microsoft repositories. Their conclusion was that the security measures introduced by Docker Inc. do not improve the overall Docker Hub security. They stated that the number of inherited vulnerabilities had dropped since the analysis of Shu et al. However, they also found that the average number of new vulnerabilities in child images had increased significantly. Further, they found that the majority of official, community, and certified repositories contain up to 75 vulnerabilities and that the majority of verified images contain up to 180 vulnerabilities.
Our contribution. This is an extended summary of our longer and much more detailed work [8]. We scrutinized the vulnerability landscape in Docker Hub images at the beginning of 2020 within the following framework: • Images on Docker Hub belong in one of the following four types: "official", "verified", "certified", or "community"; • We used a quantitative mapping of the Common Vulnerability Scoring System (CVSS) [9] (which is a numerical score indicating the severity of the vulnerability in a scale from 0.0 to 10.0) into five qualitative severity rating levels: "critical", "high", "medium", "low", or "none" plus one additional level "unknown".
For performing the analysis of a significant number of images, we used an open-source vulnerability scanner tool and developed our own scripts and tools. All our developed scripts and tools are available from [8] and from Image type 2015 [5] 2017 [6] 2019 [7] 2020 vuln avg vuln avg vuln avg vuln avg  Official  36%  -80%  75  -170 46%  70  Community  40%  -80% 180  -150 68% 150  Verified  -----150 57%  90  Certified  -----30 82%  90   TABLE 1: A summary comparison table of results reported in 2015 [5], in 2017 [6] in 2019 [7] and in our work (2020). The sub-columns "vuln" contain the percentage of images with at least one high rated vulnerability and the "avg" sub-columns contain the average number of vulnerabilities found in each image type.
Our findings can be summarized as follows: 1. The median value (when omitting the negligible and unknown vulnerabilities) is 26 vulnerabilities per image. 2. Most of the vulnerabilities were found in the medium severity category. 3. Around 17.8% (430 images) do not contain any vulnerabilities, and if we are considering negligible and unknown vulnerabilities as no vulnerability, the number increase to as many as 21.6% (523 images). 4. As intuitively expected, when considering the average, community images are the most exposed. We found that 8 out of the top 10 most vulnerable images are community images. 5. However, to our surprise, the certified images are the most vulnerable when considering the median value. They had the most high rated vulnerabilities as well as the most vulnerabilities rated as low. As many as 82% of certified images contain at least either one high or critical vulnerability. 6. Official images come out as the most secure image type. Around 45.9% of them contain at least one critical or high rated vulnerability. 7. The median value of the number of critical vulnerabilities in images is almost identical for all four image types. 8. Verified and official images are the most updated, and community and certified images are the least updated. Approximately 30% of images have not been updated for the last 400 days. 9. There is no correlation between the number of vulnerabilities and the evaluated image features (i.e., the number of pulls, the number of stars, and the last update time). However, the images with many vulnerabilities generally have few pulls and stars. 10. Vulnerabilities in the Lodash library and vulnerabilities in Python packages are the most frequent and most severe. The top five most severe vulnerabilities are coming from two of the most popular scripting languages, JavaScript and Python. 11. Vulnerabilities related to execution of code and overflow are the most frequently found critical vulnerabilities. 12. The most vulnerable package is the jackson-databind-2.4.0 package, with overwhelming 710 critical vulnerabilities, followed by Python-2.7.5 with 520 critical vulnerabilities.
Last but not least, when put in comparison with the three previous similar studies [5]- [7], our results are summarized in Table 1. Note that some of the cells are empty due to differences in methodologies and types of images when the studies were performed.

Preliminaries
Virtualization is the technique of creating a virtual abstraction of some resources to make multiple instances run isolated from each other on the same hardware [10]. There are different approaches to achieve virtualization. One approach is using Virtual Machines (VMs). A VM is a virtualization of the hardware at the host. Hence, each VM has its own kernel, and in order to manage the different VMs, a software called hypervisor is required. The hypervisor emulates the Central Processing Unit (CPU), storage, and Random-Access Memory (RAM), among others, for each virtual machine. This allows multiple virtual machines to run as separate machines on a single physical machine.
In contrast to VMs, containers virtualize the Operating System (OS) level. Every container running on the same machine shares the same underlying kernel, where only bins, libraries, and other run time components are executed exclusively for a single container. In short, a container is a standardized unit of software that contains all code and dependencies [11]. Thus, containers require less memory and achieve a higher level of portability than VMs. Container technology has simplified the software development process as the code is portable, and hence what is run in the development department will be the same as what is run in the production department [12].
On the Docker Hub, image repositories are divided into different categories. Repositories are either private or public and could further be either official, community or a verified repository. In addition, repositories could be certified, which is a subsection of the verified category. The official repositories are maintained and vetted by Docker. Docker vets the verified ones that are developed by third-party developers. Besides being verified, certified images are also fulfilling some other requirements related to quality, support, and best practices [13]. Community images could be uploaded and maintained by anyone. The distribution of the image repository types on Docker Hub can be seen in Table 2. The community repository category is by far the most dominant one and makes up to ≈99% of all Docker Hub repositories.

Vulnerability databases and categorization method
The severity of vulnerabilities depends on a variety of different variables, and it is highly complex to compare them due to the diversity of different technologies and solutions. Already in 1997, the National Vulnerability Database (NVD) started working on a database that would contain publicly known software vulnerabilities to provide a means of understanding future trends and current patterns [14]. The database can be useful in the field of security management when deciding what software is safe to use and for predicting whether or not software contains vulnerabilities that have not yet been discovered. Common Vulnerabilities and Exposures (CVE). National Vulnerability Database (NVD) contains Common Vulnerabilities and Exposures (CVE) entries and provides details about each vulnerability like vulnerability overview, Common Vulnerability Scoring System (CVSS), references, Common Platform Enumeration (CPE) and Common Weakness Enumeration (CWE) [15].
CVE is widely used as a method for referencing security vulnerabilities that are publicly known in released software packages. At the time of writing, there were 130,094 entries in the CVE list. 4 The CVE list was created by MITRE Corporation 5 in 1999, whose role is to manage and maintain the list. They work as a neutral and unbiased part in order to serve in the interest of the public. Examples of vulnerabilities found in CVE are frequent errors, faults, flaws, and loopholes that can be exploited by a malicious user in order to get unauthorized access to a system or server. The loopholes can also be used as propagation channels for viruses and worms that contain malicious software [16]. Over the years, CVE has become a recognized building block for various vulnerability analysis and security information exchange systems, much because it is continuously maintained and updated, and because the information is stored with accurate enumeration and orderly naming. Common Vulnerability Scoring System (CVSS). The Common Vulnerability Scoring System (CVSS) score is a numerical score indicating the severity of the vulnerability on a scale from zero to 10, based on a variety of metrics. The metrics are divided into three metric groups: Base Metric Group, Temporal Metric Group, and Environmental Metric group. A Base Score is calculated by the metrics in the Base Metric Group, and is independent of the user environment and does not change over time. The Temporal Metrics take in the base score and adjusts it according to factors that do change over time, such as the availability of exploit code [9]. Environmental Metrics adjust the score  This allows organizations to adjust the score related to their IT assets, taking into account existing mitigations and security measures that are already in place in the organization.
In our analysis, it would not make sense to take into account the Temporal or Environmental Metrics as we wanted to discuss the vulnerability landscape independently of the exact time and environment. Therefore, only the Base Metric group will be described in more detail. It is composed of two sets of metrics: the Exploitability metrics and the Impact metrics, as can be seen in Figure  1 [9]. The first set takes into account how the vulnerable component can be exploited and includes attack vector and complexity, what privileges are required to perform the attack, and whether or no user interaction is required. The latter set reflects on the consequence of a successful exploit and what impact it has on the confidentiality, integrity, and availability of the system. The last metric is scope, which considers if the vulnerability can propagate outside the current security scope.
When the Base Score of a vulnerability is calculated, the eight different metrics from Figure 1 are being considered. Each metric is assigned one out of two to four different values, which is used to generate a vector string. The vector string is then used to calculate the Common Vulnerability Scoring System (CVSS) score, which is a numerical value between 0 and 10. In many cases, it is more beneficial to have a textual value than a numerical value. The CVSS score can be mapped to qualitative ratings where the severity is categorized as either critical, high, medium, low, or none, as can be seen in Table 3 [9].

The distribution of vulnerabilities in each severity category
To determine what the current vulnerability landscape is like in Docker Hub, the number of vulnerabilities found in each severity category is presented in figure 2. As it is interesting to see how many vulnerabilities that are found in total (figure 2a) and how many unique vulnerabilities (figure 2b) there are, both these results are presented in this section.
In figure 2a, the results are based on vulnerability scanning of the complete data set, meaning that this result is based on all found vulnerabilities. The same vulnerability could potentially have multiple entries in the result. This is because a particular vulnerability could be found in multiple images and a single image could contain the same vulnerability in multiple packages. In figure 2b, only unique vulnerabilities are shown. However, some vulnerabilities are present in several severity categories, depending on which image it is found in. In cases like this, all versions of the vulnerability is included, which makes up a total of 14,031 vulnerabilities.
In figure 2a, the negligible and unknown categories clearly stands out, with a total of 315,102 and 240,132 vulnerabilities, respectively. When considering unique vulnerabilities (figure 2b), the medium category is the most dominant one with 5,554 unique vulnerabilities. When examining the relation between figure 2a and 2b, one can observe the ratio of vulnerabilities between severity categories. It becomes clear that the negligible category contains a few number of unique vulnerabilities represented in many Docker images. Whereas the medium category has many unique vulnerabilities represented at a lower ratio. The vulnerability ratio will be explained in detail in the next paragraph.   Table 4 shows the total number of vulnerabilities, the number of unique vulnerabilities, and the ratio, measured as the total number of vulnerabilities divided by the number of unique vulnerabilities. So, for each unique vulnerability, there are a certain number of occurrences of the specific vulnerability in the data set. For example, for each unique vulnerability in the critical category, there are 50 occurrences of this vulnerability in the data set on average. For each unique negligible vulnerability, there are as many as 329 occurrences on average. This is significantly larger than the other values. Despite medium having the highest number of unique vulnerabilities, it has the lowest ratio.

Central tendency of the vulnerability distribution
We have looked at the average and median values of the number of vulnerabilities in images when disregarding the vulnerabilities that are categorized as negligible and unknown. Looking at Table 4 from the previous section, one can see that negligible and unknown vulnerabilities together make up 555,234 out of the 918,792 vulnerabilities (around 60%). As vulnerabilities in these two categories are considered to contribute with little threat when investigating the current vulnerability landscape, it gives a more accurate result to exclude these. Therefore, we calculated the average and median number of vulnerabilities in images when disregarding negligible and unknown vulnerabilities (counting them as zero). The result was 151 for the average and 26 for the median.
To investigate the data when disregarding the negligible and unknown vulnerabilities further, we created  (158, and 6,509, respectively). The maximum value for community images is significantly larger than the average and the median, which is the case for the other three image types as well. The image type that is considered as the least vulnerable is official. It has the lowest average of 73 and the lowest median value of 9. Further, the maximum value for official images is the second lowest. The lowest maximum value belongs to certified, and is only 428. Although certified has the lowest maximum value, it has the highest median value. This indicates that a larger portion of the images have many vulnerabilities. As a final note, all four image types contain at least one image with zero vulnerabilities.

Vulnerabilities in each image type
Since the median describes the central tendency better than the average when the data is skewed here we will work with the median values (given in Figure 3). Note that only critical, high, medium and low vulnerabilities are included in the figure. The negligible and unknown vulnerabilities are not included here because they do not usually pose as significant threats, and therefore do not contribute with additional information when investigating the current vulnerability landscape.
The results show that the median of critical vulnerabilities is almost the same for all four image types (4.0 and 3.0). The other severity categories are more varied across the image types. The high severity category is the most represented in certified images, while the medium Figure 3: Median values of vulnerabilities for each severity category and image type category is the most represented in the community images. For verified, official and community images, the medium severity has the highest median, while the certified images has the most low vulnerabilities. Overall, it is the certified images that are the most vulnerable.

Images that contain the most critical vulnerabilities
Out of all 2,412 successfully analyzed images, this section will present the most vulnerable ones. Table 6 displays the most vulnerable images based on the number of critical vulnerabilities in each image. In cases where the critical count is the same, the image with the highest number of high rated vulnerabilities is considered as the most vulnerable one. The Number of pulls column denotes the total number of pulls (downloads) for each image.
Out of the top 10 most vulnerable images, there are 8 community images, 1 official image (silverpeas) and 1 verified image (microsoft-mmlspark-release). There are big variations in the number of vulnerabilities in all presented severity levels. The most vulnerable image,   Figure 4: The percentage of images that contain at least one high or critical rated vulnerability.
pivotaldata/gpdb-pxf-dev, has~250 more critical vulnerabilities than the second most vulnerable image. However, the second most vulnerable image, cloudera/quickstart, contains as many as 2,155 high rated vulnerabilities, which is~1500 more vulnerabilities than the one rated as the most vulnerable image. It was chosen to focus on the critical vulnerabilities in the ranking of the most vulnerable images. This is because it is the highest possible ranking and hence the most severe vulnerabilities will be found in this category. The other severity categories are included in the table as extra information and to give a clear view on the distribution of vulnerabilities. From the number of pulls column one can observe that the most vulnerable image is also the most downloaded one out of the top 10, with as many as 139,246,839 pulls. This is approximately 100 million more pulls compared to the second most pulled image on this list (the raphacps/simpsons-mavenrepo image). There is no immediate correlation that could be observed between the number of pulls and the number of vulnerabilities in these images.

Percentage of images with critical and high vulnerabilities
It is enough with a single vulnerability for a system to be compromised. Thus, we determine what percentage of images that contain at least one high or critical rated vulnerability for each image type, as shown in Figure 4.
Our results (Figure 4) reveal that the certified image type, which is a subsection of the verified image type, is the most vulnerable by the means of this measure. 81.8% of all certified images contain at least one vulnerability with high severity level and 72.7% of them contain at least one critical vulnerability. Community images come out as the second most vulnerable image type. 67.4% have high vulnerabilities and 45.1% have critical vulnerabilities. The third most vulnerable image type is verified, followed by official.
When combining these results, to investigate what amount of the image types that contain either at least one critical or high rated vulnerability, the results are as follows: 81.8% for certified images, 68.4% for community images, 56.7% for verified images and 45.9% for official images. This makes the official images the least vulnerable image type. However, it should be emphasized that still almost half of the official images contain critical or high rated vulnerabilities as presented in this section.

The trend in CVE vulnerabilities
This section will focus on the trend of all reported Common Vulnerabilities and Exposures (CVE) vulnerabilities each year compared to the number of unique CVE vulnerabilities found throughout our analysis. Data gathered from the CVE Details database [17]

Days since last update
There is a high variation in how often Docker Hub images are updated. Intuitively, this affects the vulnerability landscape of Docker Hub. Hence, we have gathered data about when images were last updated, and calculated the number of days since the images were last updated, counting back from February 25th, 2020. The data set consists of last updated data for all analyzed images, except five.
A brief analysis of the numbers from our database revealed that 31.4% of images have not been updated in 400 days or longer and 43.8% have not been updated in 200 days or longer. The percentage of images that have been updated during the last 14 days are 29.8%. This implies that if these numbers are representative for all images on Docker Hub, a third of the images (31.4%) on Docker Hub have not been updated in the last 400 days or longer.
To go into more detail, Table 7 presents how often images in each of the image types are updated. Community and certified images are the least updated image categories, where 47.0% of community images and 36.4% of certified images have not been updated for the last 200 days or more. The verified images are the most frequently updated category, where 83.3% of images have been updated during the last 14 days.
A handful of certified images are highly affecting the percentages from Table 7, because the overall number of certified images is small. Official images contain a high portion of images that have been updated recently (January 2020 to March 2020), and some more spread values with images that have not been updated since 2016. The verified images are the most updated image type, where there is only one image with the last updated time earlier than May 2019.

Correlation between image features and vulnerabilities
We investigate whether or not the number of vulnerabilities in an image is affected by a specific image feature, such as the number of times the image has been pulled, the number of stars an image has been given, or the number of days since the image was last updated. In order to find out whether there is a correlation, we used Spearman's r s correlation coefficient [18]. Spearman's correlation was chosen because our data set contain skewed values and are not normally distributed. When handling entries that contained empty values, we opted for the approach of complete case analysis, which means omitting incomplete pairs. The alternative would be imputation of missing values, which means to create an estimated value based on the other data values. However, this approach was not chosen because the values of our data set are independent of each other.
Correlation between pulls and vulnerabilities. To check the folklore wisdom about the following correlation: images with the most pulls generally have few vulnerabilities, and images with the most vulnerabilities generally have few pulls, we created a scatter plot given in Figure  6. However, after calculating the Spearman correlation coefficient between the number of pulls and number of vulnerabilities for the whole set of investigated images we got r s = −0.1115. This is considered as no particular correlation. To explain this, we refer to the meaning of Correlation between stars and vulnerabilities. The correlation coefficient between the number of stars and number of vulnerabilities is r s = −0.0335. Figure 7 shows the scatter plot when including number of stars instead of number of pulls. The plot is similar to Figure  6, but the correlation is even weaker. Correlation between time since last update and vulnerabilities. This correlation is calculated by computing the number of days since the last update counting from the day we gathered the data (which was February 25, 2020). The correlation was r s = 0.1075, which shows a positive correlation as opposed to the other two. Figure 8 shows the scatter plot, and although the markers are approaching an increasing line a tiny bit, this is minimal. The value of 0.1075 is still not enough to state that there is a strong correlation between the number of vulnerabilities and time since the last update. The markers slightly approach an increasing line, indicating a weak tendency that there are more vulnerabilities in images that have not been updated for a long time. Still, the distribution of markers is relatively even along the x-axis with the most markers in the lower part of the y-axis, supporting that there is no correlation.

The most represented critical vulnerabilities
The most represented severe vulnerabilities are, intuitively, the ones having the highest impact on the vulnerability landscape. Table 8 presents the most represented critical rated vulnerabilities in descending order. The results are obtained by counting the number of occurrences for each vulnerability ID in the critical severity level. The critical count column is the number of occurrences for a specific vulnerability. Lastly, the type(s) column presents the vulnerability type of each of the vulnerabilities. This data is gathered from the CVE Details database [19].

Vulnerability characteristics
We elaborate the top five most represented vulnerabilities presented in Table 8 regarding their characteristics and common features 6 . The top five severe vulnerabilities are coming from two most popular script languages: JavaScript and Python. As a general observation, the execute code is the most common vulnerability type, followed by overflow.
The most represented critical vulnerability is found 466 times throughout our scanning. It has vulnerability ID CVE-2019-10744, and a base score of 9.8, which is in the upper range of the critical category (to examine how base scores are determined, see Section 2.1). The vulnerability is related to the JavaScript library lodash, which is commonly used as a utility function provider in relation to functional programming. This particular vulnerability is related to improper input validation and makes the software vulnerable to prototype pollution. It is affecting versions of lodash lower than 4.17.12 [20]. In short, this means that it is possible for an adversary to execute arbitrary code by modifying the properties of the Object.prototype. This is possible as most JavaScript objects inherit the properties of the built in Object.prototype object. The fifth vulnerability on the list, CVE-2018-16487, is also related to lodash and the prototype pollution vulnerability.
Further, the second, third and fourth most represented critical vulnerabilities are related to Python vulnerabilities. The second vulnerability with vulnerability ID, CVE-2017-1000158, is related to versions of Python up to 2.7.13. The base score is rated 9.8, and the vulnerability enables arbitrary code execution to happen through an integer overflow leading to a heap-based buffer overflow [21]. Overflow vulnerabilities could be of different types, for instance heap overflow, stack overflow and integer overflow. Heap overflow and stack overflow are related to overflowing a buffer, whereas integer overflow could lead to a buffer overflow. A buffer overflow is related to overwriting a certain allocated buffer, causing adjacent memory locations to be overwritten. Any exploit of these kinds of vulnerabilities are typically related to the execution of arbitrary code, where the adversary is taking advantage of the buffer overflow vulnerability to run malicious code.
The third presented vulnerability with vulnerability ID CVE-2019-9948 is affecting the Python module urllib in Python version 2.x up to 2.7.16. It is rated with 9.1 as base score. This vulnerability makes is easier to get around security mechanisms that blacklist the file:URIs syntax, which in turn could give an adversary access to local files such as the /etc/passwd file [22]. The fourth vulnerability is found 374 times and has vulnerability ID CVE-2019-9636. It is affecting both the second and the third version of Python (versions 2.7.x up to 2.7.16, and 3.x up to 3.7.2). This vulnerability is also related to the urllib module, more precisely, incorrect handling of unicode encoding. The result is that information could be sent to different hosts than intended if it was parsed correctly [23]. It has a base score of 9.8. 6. Vulnerabilities in packages 6.1. The most vulnerable packages Table 9 presents the packages that contain the most critical vulnerabilities. The critical count column is obtained by counting the total number of occurrences of critical vulnerabilities in each package, while the image count column is the number of images that uses each package.
There is a clear relation between the most vulnerable packages and the most represented vulnerabilities (Section 5), as expected. For example, vulnerabilities found in Python version 2.x packages and in the Lodash package are both presented in Section 5.
From Table 9, one can observe that the Python packages are by far the most used packages, and therefore they expose the biggest impact regarding the threat landscape. The lodash-3.10.1 package is found in 76 images. This package contains the prototype pollution vulnerability affecting JavaScript code, which also is the most represented vulnerability in Table 8. Further, the jackson-databind package is represented with four different versions in Table 9 (entry 1, 3, 8 and 9). This package is used to transform JSON objects to Java objects (Lists, Numbers, Strings, Booleans, etc.), and vice versa. In total, these packages are used by 44 images: a relatively low amount compared to the usage of the Python packages. Finally, the silverpeas-6.0.2 package contains 280 critical vulnerabilities and is only used by a single image: the silverpeas image on Docker Hub. 7

Vulnerabilities in popular packages
When considering the packages that have the most critical vulnerabilities (Table 9), some of the packages are only used by a few images (like the silverpeas package). Therefore, Table 10 is presented, as it is desirable to see what the vulnerability distribution is like in the most popular packages. The table shows the most used packages and the number of vulnerabilities that are present in them, considering all security levels. The image count column contain the number of images that use this package.
As observable from Table 10, the most used packages are not containing any critical, high, medium or low vulnerabilities (except for one entry). However, they are containing a vast number of negligible vulnerabilities, which is of less significance from a security point of view, as mentioned in previous sections.

Conclusions and future work
This paper summarizes the findings that we reported in a longer and much more detailed work [8]. We studied the vulnerability landscape in Docker Hub images by analyzing 2500 Docker images of the four image repository categories: official, verified, certified images, and community. We found that as many as 82% of certified images contain at least one high or critical vulnerability, and that they are the most vulnerable when considering the median value. Official images came out as the most secure image type with 45.9% of them containing at least one critical or high rated vulnerability. Only 17.8% of the images did not contain any vulnerabilities, and we found that the community images are the most exposed as 8 out of the top 10 most vulnerable images are community images.
Concerning the technical specifics about the vulnerabilities, we found that the top five most severe vulnerabilities are coming from two of the most popular scripting languages, JavaScript and Python. Vulnerabilities in the Lodash library and vulnerabilities in Python packages are the most frequent and most severe. Furthermore, the vulnerabilities related to execution of code and overflow are the most frequently found critical vulnerabilities. Our scripts and tools are available from [8] and from the GitHub repository.
For the future work we first propose two improvements that are beyond our control, and are mostly connected with the maintenance of all 3.5 million images at the Docker Hub web site: 1. There is a need for a complete and welldocumented endpoint for image data gathering;, and 2. There is a need for improvements on the Docker Hub web pages to make it possible to access all images through navigation.
Concerning improvements of this work, we consider a future analysis that will run over a more extended period. All previous studies conducted in this field, as well as ours, have only analyzed vulnerabilities in Docker Hub images captured from one single data gathering. Thus, changes in the data set over time are still not investigated. This type of analysis could reveal more in-depth details about the characteristics and evolution of the vulnerability landscape.
Lastly, we suggest future work to be targeting the false positives and false negatives in container scanners by integrating machine learning into container scanners.


Low-latency Federated Learning and Blockchain for Edge Association in Digital Twin empowered 6G Networks

Emerging technologies such as digital twins and 6th Generation mobile networks (6G) have accelerated the realization of edge intelligence in Industrial Internet of Things (IIoT). The integration of digital twin and 6G bridges the physical system with digital space and enables robust instant wireless connectivity. With increasing concerns on data privacy, federated learning has been regarded as a promising solution for deploying distributed data processing and learning in wireless networks. However, unreliable communication channels, limited resources, and lack of trust among users, hinder the effective application of federated learning in IIoT. In this paper, we introduce the Digital Twin Wireless Networks (DTWN) by incorporating digital twins into wireless networks, to migrate real-time data processing and computation to the edge plane. Then, we propose a blockchain empowered federated learning framework running in the DTWN for collaborative computing, which improves the reliability and security of the system, and enhances data privacy. Moreover, to balance the learning accuracy and time cost of the proposed scheme, we formulate an optimization problem for edge association by jointly considering digital twin association, training data batch size, and bandwidth allocation. We exploit multi-agent reinforcement learning to find an optimal solution to the problem. Numerical results on real-world dataset show that the proposed scheme yields improved efficiency and reduced cost compared to benchmark learning method.

I. INTRODUCTION
Recent advancements in digital twins and 6th Generation mobile networks (6G) have paved the way for Industrial Internet of Things (IIoT) [1]. A series of edge intelligence use cases such as intelligent transportation [2], [3] and smart city [4] are envisioned to provide high-quality services to users in the IIoT network. Data processing based on Artificial Intelligence (AI) algorithms lays the foundation for enabling the provision of intelligent services in the IIoT framework. Despite such enabling technologies and recent developments, the gap between the outcome of data analysis and the true reflection of the status of their physical systems remains a major hurdle in designing robust control algorithms for physical systems [5]. In this regard, the digital twin paradigm [6] emerges as one of the most promising technologies in 6G networks that can enable the near-instant wireless connectivity and extreme-reliable wireless communication [7]. Empowered by digital twin, the 6G networks can bridge the physical systems with the digital world in real-time for realizing robust edge intelligence in IIoT.
Digital twins represent real objects or subjects with their data, functions, and communication capabilities in the digital space [8]. To reduce latency and enhance reliability for edge computing applications, we incorporate digital twins into wireless networks and propose the Digital Twin Wireless Networks (DTWN). By mapping IoT devices to digital twins in edge servers, DTWN improve the efficiency of AI algorithms and mitigates the impact of unreliable communication between users and edge servers. Moreover, DTWN interact with the physical IIoT systems in real-time through data collection and analytics to keep the digital plane synchronised with the physical system. Thus, the running state analysis and optimization of user devices can be conducted directly in the DTWN, which reduces the system cost. We have noted few works that discuss integrating digital twins with physical systems to improve their performance for different applications. For instance, in [8], the authors proposed the Experimentable Digital Twins (EDTs) that can be used to realize complex control algorithms or mental models. In particular, the authors constructed a general digital twin for complex equipment and proposed a new method for health management using digital twins [9]. In this paper, we propose to integrate digital twins into edge networks to mitigate the resource gap between end users and Base Stations (BSs) for efficient edge computing.
Conventional centralized AI algorithms require data to be transmitted to the server, which incurs high data leakage risks. To enhance data security and protect user privacy, federated learning [10], [11] has emerged as a new paradigm for distributed machine learning. Different from conventional AI algorithms, federated learning based models require transmitting only the parameters from locally trained models to the server while the original data is stored with the user to alleviate security and privacy risks [12]. To this end, the distributed framework and the enhanced data privacy assurance offered by federated learning have attracted considerable attention and have been well studied for typical MEC applications [13] such as content caching [14] and vehicular data sharing recently [15]. Nonetheless the need of conducting the iterative training process on distributed entities each with possibly limited computing resources can adversely affect the efficiency of federated learning in edge networks. To address the issue, in [16], the authors proposed a control algorithm to determine the trade-off between local update and global aggregation under a given resource budget. In [17], the authors formulated resource consumption and learning performance into an optimization problem and provided the approximate optimal solution.
Moreover, the lack of mutual trust among users is another key factor that can hinder them from participating in the learning process to realize edge intelligence. To deal with this issue, blockchain has been widely explored to build a secure collaborative learning mechanism among untrusted users. For example, the authors in [18] proposed a three layer-based architecture to manage reliable and secure connections among entities, processes and critical resources for the smart grid. Meanwhile, the efficiency and intelligence of blockchain needs to be further improved. Several studies have explored the synergy between AI algorithms and blockchain to enhance the data security and system reliability aspects in edge intelligence enabled networks. In [19], the authors presented an edge intelligence and blockchain empowered framework to enhance the security of edge service management in an IoT scenario. Similarly, in [20], the authors integrated blockchain with Deep Reinforcement Learning (DRL) for content caching in vehicular networks. As conventional AI algorithms can suffer much data transmission load while also leading to higher data leakage risk, we propose to integrate blockchain with federated learning to achieve secure and efficient edge intelligence. In our proposed framework, the federated learning parameters are recorded in the blockchain instead of the parameter server thus considerably enhancing the security of parameters and improving the reliability of models from users.
In our proposed framework, DTWN mitigate the unreliability of learning parameter transmission caused by long communication distance and limited communication resource between end users and edge servers (BSs). However, some new challenges also arise for the maintenance of digital twins. First is the associations of digital twins to various servers. It consumes considerable amount of resources to maintain digital twins by synchronizing real-time data and building corresponding models. Due to the dynamic computing and communication resources available with edge servers, the association of digital twins to corresponding servers is a crucial factor in determining the performance of DTWN, which is a largely unexplored dimension in the context of edge networks. Moreover, due to the multiple communication rounds in federated learning, the limited bandwidth available with BSs requires to be optimally allocated to improve the communication efficiency of associated edge servers. In this paper, we first design the new DTWN model by incorporating digital twins into wireless networks to mitigate the unreliable and long distance communication between users and BSs, where the user data is synchronized to BSs to construct corresponding digital twins. Based on the DTWN, we propose a permissioned blockchain empowered federated learning framework for realizing robust edge intelligence. Data analysis can be executed on their digital twins in the BS plane directly instead of in the resource constrained end users. The security and privacy of digital twin data are also enhanced by . To improve the efficiency of the proposed architecture, we formulate an optimization problem for edge association and bandwidth allocation, and design a multi-agent reinforcement learning based algorithm to find the optimal solution to it. The main contributions of this paper are summarized as follows.
• We design a new digital twin wireless network model-DTWN, which uses digital twins to mitigate the unreliable and long distance communication between end users and edge servers. • We define the edge association problem for DTWN, and propose a permissioned blockchain empowered federated learning framework for edge computing in DTWN. • To improve the efficiency of the proposed scheme, we formulate an optimization problem by jointly considering edge association and communication resource allocation to minimize the time cost, and develop a multi-agent reinforcement learning based algorithm to find the optimal solution to the problem. The rest of the paper is organized as follows. In Section II, the blockchain and federated learning model for DTWN is provided. In Section III, we formulate a new edge association problem in DTWN to minimize the total system latency. A multi-agent reinforcement learning based algorithm is developed to find the optimal solution to the problem in Section IV. Numerical results are presented in Section V. Finally, Section VI concludes the paper.

II. BLOCKCHAIN AND FEDERATED LEARNING MODEL
FOR DIGITAL TWIN NETWORKS In this section, we first present our DTWN model. Then we describe the edge association problem in DTWN in Section II-A, which is followed by the federated learning model in Section II-B. Then we introduce our blockchain model in Section II-C and the wireless communication model in Section II-D.
We consider a blockchain and federated learning empowered digital twin network model as depicted in Fig. 1. The system consists of N end users such as IoT devices and mobile devices, M BSs, and a Macro Base Station (MBS). The BSs and the MBS are equipped with MEC servers. The end devices generate running data and synchronize their data with corresponding digital twins that run on the BSs. We use .., (x iDi , y iDi )} to denote the data of end user i, where D i is the data size, x i is the data collected by end users and y i is the label of x i . The digital twin of end user i in the BSs are denoted as DT i , which is composed of behavior model M i , static running data D i and realtime dynamic state s t , DT i = (M i , D i , s t ). D i and s t is the essential data required to run digital twin applications. Instead of synchronizing all raw data to digital twins, which incurs great communication load and data leakage risk, we use federated learning to learn model M from user data. In various application scenarios, the end users may communicate with other end users to exchange running information and share data, through e.g., Device to Device (D2D) communications. Thus, the digital twins also form a network based on the connections of end users. Based on the constructed DTWN, we can obtain the running states of physical devices and make further decisions to optimize and drive the running of devices by analyzing digital twins directly.
In our proposed digital twin network model, we use federated learning to execute the training and learning process collaboratively for edge intelligence. Moreover, since the end users lack mutual trust and the digital twins consist of private data, we use permissioned blockchain to enhance the system security and data privacy. The permissioned blockchain records the data from digital twins and manages the participating users through permission control. The blockchain is maintained by the BSs, which are also the clients of the federated learning model. The MBS runs as the server for the federated learning model. In each iteration of federated learning, the MBS distributes the machine learning model parameters to BSs for training. The BSs train the model based on data from digital twins and returns the model parameters to the MBS.

A. Edge Association in DTWN
The end devices or users are mapped to the digital twins in BSs in DTWN. The maintenance of digital twins consumes a large amount of computing and communication resources for synchronizing real-time data and building corresponding models. However, the computation and communication resources in wireless networks are very limited, which should be optimally used to improve the resource utility. Thus, to associate various IoT devices with different BSs according to their computation capabilities and states of the communication channel, is a key problem in DTWN. As depicted in Fig. 1, The digital twins of IoT devices are constructed and maintained by their associated BSs. The training data and the computation tasks for training are distributed to various BSs based on the association between digital twins and the BSs. We provide the formal definition of the edge association in Definition 1.
Definition 1 (Edge Association): Consider a DTWN with N IoT users and M BSs. For any user u i , i ∈ N , the goal of edge association is to choose the target BS j ∈ M to construct the digital twin DT i of user i. The association A BS can associate with multiple digital twins, while a digital twin can only be associated with at most one BS. That is, M j=1 Φ(i, j) = D i . We perform edge association according to the datasets D i of IoT users, the computation capability of BSs f j , and the transmission rate R i,j between u i and BS j , denoted as The objective of the edge association problem is to improve the utility of resources and the efficiency of running digital twins in the DTWN.

B. Federated Learning Model
The goal of federated learning is to train a global machine learning model M based on the data from various digital twins DT i without transmitting the original training data. The learning process involves finding the parameter w for global model M that minimizes the global loss function f (w, x, y), denoted as The client BSs train their local models based on their own data. Each client minimizes the loss function on its local data through gradient descent based methods such as gradient descent and stochastic gradient descent, with a predefined learning rate. The clients then transmit the local gradients or the local models to the server MBS to update the global model, through algorithms such as federated averaging (FedAvg) [10] and Federated SGD (FedSGD). We denote the aggregation of the global model as: In the training process, the BSs train the local models based on the digital twins DT i that they maintained according to Eq. 2. A BS may contain several digital twins constructed from the end users under its coverage. Different from conventional federated learning, the BSs in our proposed scheme first aggregate their local models from multiple digital twins instead of sending the original local models to the MBS, which can reduce the transmission load. As BS m has K i digital twins, the aggregation at BS i is where D DTi is the training data of digital twin DT i and w DTi is the trained model of DT i . BS m then sends G m to the MBS, and the MBS updates the global model as The local models of digital twins are transmitted to the MBS through wireless links. The MBS collects the model parameters from all participating BSs and updates the global model. In this process, since all BSs transmit their parameters in the same period and the wireless bandwidth is limited, the communication efficiency is of vital importance for the learning phase to converge.

C. Blockchain Model
To enhance the security and reliability of digital twins from untrusted end users, the BSs act as the blockchain nodes and maintain the running of the permissioned blockchain. The digital twins are stored in the blockchain and their data is updated as the state of the corresponding user changes. Moreover, the local models of the BS are also stored in the blockchain, which can be verified by other BSs to ensure the quality of local models. Thus, there are three types of records, namely, digital twin model records, digital twin data records, and training model records.
The overall blockchain scheme for federated learning is shown in Fig. 2. The BSs first train the local training models on their own data, and then upload the trained models to the MBS. The trained models are also recorded as blockchain transactions, and broadcasted to other BSs for verification. Other BSs collect the transactions and pack them into blocks. The consensus process is executed to verify the transactions in blocks. Our consensus process is executed based on Delegated where S ini is an initial value, K i is the number of digital twins associated to BS i.
The coins of each BS are then adjusted according to their performance in the training process. If the trained model of a BS passes the verification of other BSs and the MBS, coins will be awarded to the BS. Otherwise, the BS will get no pay for its training work. A number of BSs are elected as the block producers by all BSs. In the voting process, all the BSs vote for the candidate BSs by using their own training coins. The elected BSs take turns to pack the transactions in a time interval T into a block B, and broadcast block B to other producers for verification.
In our federated learning scheme, we leverage blockchain to verify the local models before embedding them into the global model. Due to high resource consuming for block verification, the interval T should be set to multiple times of the local training period, that is, the BSs execute multiple local training iterations before transmitting local models to the MBS for global aggregation.

D. Communication Model
We use the Orthogonal Frequency Division Multiple Access (OFDMA) for wireless transmission in our system. To upload trained local models, all BSs share C sub-channels to transmit their parameters. The achievable uplink data rate from BS i to the MBS is: where C is the total number of subchannels, τ i,c is the time fraction allocated to BS i on subchannel c, W U is the bandwidth of each subchannel which is a constant value. The transmission power is P U i,c and the uplink channel gain on subchannel c is h U i,c . r −α i,m is the path loss fading of the channel between BS i and the MBS, r i,m is the distance between BS i and the MBS, and α is the path loss exponent. N 0 is the noise power and j∈N P U j,c h U j,c r −α i,m is the interference caused by other BSs using the same subchannel. In the download phase, the MBS broadcasts the global model with the rate where P D i,c is the downlink power of BS i and h D i,c is the channel gain between BS i and the MBS, is the downlink inference.

III. EDGE ASSOCIATION IN DTWN: PROBLEM FORMULATION
In this section, we first analyze the delay performance of the proposed model, and then formulates the optimization problem for edge association in DTWN to minimize the total system time cost under the given learning accuracy requirement. Now we start to derive the formulation of edge association problem. We consider that the gradient ∇f (w) of f (w) is L-Lipschitz smooth, that is where L is a positive constant and ||w t+1 −w t || is the norm of w t+1 −w t . We consider that the loss function f (w) is strongly convex, that is (10) Many loss functions for federated learning can satisfy the above assumptions, for example, the logic loss functions. If (9) and (10) are satisfied, the upper bound of global iterations can be obtained as [21] T where θ L is the local accuracy ||∇f (wt+1)|| ||∇f (wt)|| ≤ θ L , θ G is the global accuracy, and 0 ≤ θ L , θ G ≤ 1. As in [17], we consider θ L as a fixed value, so that the upper bound T (θ L , θ G ) can be simplified to T (θ G ) = 1 1−θ G . Denote the time of one local training iteration by T cmp , then the computation time in one global iteration is log(1/θ)T cmp , and the upper bound of total learning time is T (θ G )T glob .
The time cost in our proposed scheme mainly consists of 1) Local training on digital twins: The time cost for the local training of BS i is decided by the computing capability and the data size of its digital twins. The time cost is where f C is the number of CPU cycles required to train one sample of data, f C i is the CPU frequency of BS i, b j is the training batchsize of digital twin DT j . 2) Model aggregation on BSs: The BSs aggregate its local models from various digital twins according to Eq. (4). The computing time for local aggregation is where |w j | is the size of local models and f C b is the number of CPU cycles required to aggregate one unit of data. Since all the clients share the same global model, |w 1 | = |w 2 | = ... = |w j | = |w g |. Thus the time cost for local aggregation is 3) Transmission of model parameters: The local models aggregated by BS i are then broadcasted to other BSs as transactions. The time cost is related to the number of blockchain nodes and the transmission efficiency. Since other BSs also help to transmit the transaction in the broadcast process, the time function is related to log 2 M , where M is the size of the BS network. The required time cost is where ξ is a factor of transmission time cost that can be obtained from historical running records of the transmission process.

4) Block Validation:
The block producer BS collects the transactions and packs them into a block. The block is then broadcasted to other producer BSs, and validated by them. Thus, the time cost is where M p is the number of block producers, S B is the size of a block.
Note that in the aggregation phase, the size of model parameters |w g | is small and the computing capability f i is high. Thus, compared to other phases, the time for aggregation is very small that can be neglected. Based on the above analysis, the time cost for one iteration is denoted as In the 6G network, the growth of the user scale, the ultra-low latency requirement of communication, and the dynamic network status make it an important issue to reduce the time cost of model training in various applications. Since accuracy and latency are two main metrics to evaluate the decision making abilities of digital twins in our proposed scheme, we consider the edge association problem to find the trade-off between learning accuracy and time cost of the learning process. Due to the dynamic computing and communication capabilities of various BSs, the edge association of digital twins, that is, how to allocate the digital twins of different end users to various BSs for training, is a key issue to be solved for minimizing the total time cost. Moreover, increasing the training batch size b n of each digital twin DT n can improve the learning accuracy. However, it will also increase the learning time cost to execute more computation. In addition, how to allocate the bandwidth resources to improve the communication efficiency, should also be considered. In our edge association problem, we should carefully design these policies to minimize the total time cost of the proposed scheme. Thus, we formulate the optimization problem as minimizing the time cost of federated learning under a given learning accuracy. To solve the problem, the association of digital twins, the batchsize of their training data, the bandwidth allocation should be jointly considered according to the computing capability f C i and the channel state h i,c . The optimization problem can be formulated as min Ki,bn,τi,c Constraint (18b) ensures that the sum of the number of associated digital twins does not exceed the size of total dataset. Constraint (18c) guarantees that each subchannel can only be allocated to at most one BS. Constraint (18d) ensures the range of training batch size for each digital twin. Problem (18) is a combinational problem. Since there are several products of variables in the objective function, and the time cost of each BS is also affected by the resource states of other BSs, it is challenging to solve problem (18).

IV. MULTI-AGENT DRL FOR EDGE ASSOCIATION
Since the system states are only determined by network states in the current iteration and the allocation policies in the last iteration, we regard the problem as a Markov Decision Process (MDP) and use multi-agent DRL [22] based algorithm to solve it.

A. Multi-agent DRL Framework
The proposed multi-agent reinforcement learning framework is shown in Fig. 3. In our proposed system, each BS is regarded as a DRL agent. The environment consists of BSs and digital twins of end users. Our multi-agent DRL framework consists of multiple agents, a common environment, system state S, action A and the reward function R, which are described below. where each dimension is a state vector that contains the states for all agents. • Action space: The actions of BS i in our system consist of the digital twin allocation K i , the training data batchsizes for its digital twins b i , and the bandwidth allocation τ i . Thus, the actions are denoted as a i (t) = (K i , b i , τ i ). BS agent i makes new action decisions a i (t) at the beginning of iteration t based on system state s(t). The system action is a(t) = (a 1 , ..., a i , ..., a m ).
• Reward: We define the reward function of BS i according to its time cost T i based on Eq. (17), as The reward vector of all agents is R = (R 1 , ..., R m ). According to Eq. (18), the total time cost T is decided by the maximum time cost of agents max{T 1 , T 2 , ..., T m }. Thus each DRL agent shares the same reward function in our scheme. In the training process, the BS agents adjust their actions to maximize the reward function, that is, to minimize the system time cost in each iteration.
The learning process of BS i is to find the best policy that maps its states to its actions, denoted as a i = π i (s), where a i is the action to be taken by BS i for the whole system state s. The objective is to maximize the expected reward, that is where γ is the discount rate, 0 ≤ γ ≤ 1. In the conventional DRL framework, it is hard for an agent to obtain the states of others. In our DTWN, the states of digital twins and BSs are recorded in the blockchain. A BS can retrieve records from blockchain to obtain the system states and actions of other agents in the training process.

B. Multi-agent DRL algorithm for edge association
Since the network states variable such as h and f C are continuous values, the state and action spaces are large. We adopt Deep Deterministic Policy Gradient (DDPG) algorithm to address the formulated MDP problem. The DDPG algorithm uses policy-based Actor-Critic (AC) to select and evaluate the actions, and uses Deep Q Networks (DQNs) to approximate value functions in actor and critic networks. The multiple agents share the same reward function and train their policy network cooperatively to minimize the time cost.
In the training phase, each BS agent generates the training sample s, a i , R i , s , where s is the state of DTWN in the next time slot. We leverage DQN with the tuples randomly sampled from replay memory to train the actor network π(s t |θπ) and critic network Q(s t , a i |θ Q ), with parameters θ π and θ Q . There are two sets of actor and critic networks-the primary networks and the target networks. The target networks have the same structure as the primary networks and are used to generate target values for training primary networks.
Each agent i has a actor DNN π(s t |θ π ) to determine its action a i based on current state s t , as where N is the random noise generated by the Ornstein-Uhlenbeck process [23], θ πi is the explored edge association policy. The parameters of the primary actor DNN are updated as where α π is the learning rate of the actor DNN. We train the primary critic network of agent i by taking steps in the opposite gradient direction of the loss function as where α Qi is the learning rate of the primary critic DNN, and y t is the target value generated by target networks, (a 1 , ..., a i ) are the actions of all DRL agents.
The target networks represent the old version of the primary networks. The parameters of the target action DNN θ T π and the target critic DNN θ T Q are trained in a different way. Agent i updates its target action DNN θ T πi and critic DNN θ T Qi as where β is the update rate. The proposed multi-agent reinforcement learning algorithm for edge association problem is summarized as Algorithm 1. Each agent first initializes its primary and target critic-actor DNNs, and initializes the edge association policy. Then, the primary actor DNN of agent i generates action a i based on current state and policy according to Eq. (21). The observed reward R i (e) and next state s t+1 are calculated, and the tuple (s t , a, R i (e), s t+1 ) is stored into the replay memory as training samples. The primary actor DNN and critic DNN are then updated based on Eq. (22) and Eq. (23). The target networks are updated according to Eq. (24). Initialize primary and target actor-critic networks; Initialize replay memory; 3: end for 4: for each BS i ≤ M do 5: for episode e ≤ E do 6: Initialize DTWN environment setup; 7: for each time slot t do 8: Observe current state s and execute action a i according to Eq. (21); 9: Compute reward R i (t), and transit to the next state s t+1 based on actions (a 1 , a 2 , ..., a n ) 10: Store (s t , a i (t), R i (t), s t+1 ) into replay memory 11: Update primary actor and critic networks according to Eq. (22)  The computation cost training process of the DRL can be performed offline for large number of episodes based on the dynamic system states. The trained DRL models are deployed online to optimally allocate the resources to minimize the time cost of federated learning under given learning accuracy. The actions in our multi-agent DRL for edge association are composed of digital twin association policies K, batchsize of training data b, and the bandwidth allocation policies τ . Due to the large action and state space, we adopt the actor DNN to generate actions. The complexity of our proposed learning algorithm mainly lies in the training process of actor DNN θ π and critic DNN θ Q . Consider the DNN in our algorithm has L hidden layers, and the average number of neurons in each layer is L a . Thus the time complexity for training a DNN is O(L 2 a ). The total complexity for training the multi-agent DRL model with M agents is O((M · L 2 a ) · E). Since the training at each agent is executed in parallel, the time complexity is O(L 2 a · E), which is related to the DNN size and the number of episodes.

V. NUMERICAL RESULTS
We conduct our experiment on a real-world dataset CI-FAR10 [24]. The CIFAR10 dataset consists of 60,000 images in 10 classes, including 50,000 training images and 10,000 test images. Learning on the image dataset simulates the real edge computing scenarios such as traffic flow monitoring and image recognition of smart cameras. We consider a wireless network with 1 MBS, 5 BSs, and 100 end users. The users are randomly distributed in the coverage area of BSs, as shown in Fig. 4. The CIFAR10 dataset is shuffled and assigned to the end users randomly. Thus the training data of federated learning is Independent and Identically Distributed (IID) in our experiment. The Convolutional Neural Network (CNN) [25] is adopted as the machine learning model for federated learning. The CNN model has two 5 × 5 convolution layers (with 32 channels and 64 channels, respectively) and 2 × 2 max-pooling layers, followed by a fully connected layer with 512 units. The maximum CPU frequencies of five BSs are 2.6GHz, 1.8GHz, 3.6GHz, 2.4GHz, and 2.4GHz, respectively. The transmission power of RSUs and the MBS is 34dBm and 42dBm, respectively. The bandwidth of the subchannel is set as 30MHz. N 0 is set to -174 dBm. The latency performance with respect to training rounds is shown in Fig. 5 for our proposed algorithm and the conventional learning algorithms with random edge association and with average edge association. Our proposed algorithm significantly reduces the system time cost compared with the benchmark algorithms. The multi-agent reinforcement learning algorithm optimizes digital twin association, and optimally allocates communication resources, which improves the running efficiency and reduces the system latency for our scheme. Fig.  6 depicts the learning performance of the proposed algorithm, compared with the learning algorithm with full training data and the learning algorithm with random edge association. From the results we can see that our proposed algorithm achieves a comparable convergence performance compared to fully trained federated learning, where all training data of users is utilized in each training process. The learning loss of our proposed algorithm is improved through the optimization process compared with the conventional algorithm with random edge association.  , where R i,t is the total reward of agent i in episode t, and M is the number of agents. The cumulative average time cost of our proposed multi-agent deep reinforcement learning are depicted in Fig. 7 for different values of the discount factor γ. The cost of different γ converges as the number of iterations increases, which denotes that the training process of the DRL model has maximized the cumulative reward and has minimized the system time cost. The curve with γ = 0.9 achieves the best performance, which has a higher convergence rate and smaller system time cost. The time cost for running our reinforcement learning based optimization algorithm is shown in Fig. 8. We can see that the training of our proposed optimization algorithm costs much more time than the test phase. The reason is that the training of deep reinforcement learning model is a process of iterative exploration. The agents take much time to interact with the environment to learn optimal policies. Although there are some fluctuations in the result curves, the overall time cost for training or testing in each iteration is comparable. The time is consumed mainly by the training process of the deep neural networks in reinforcement learning. From Fig. 8 we can also see that a larger discount factor γ slightly leads to a larger time cost in each iteration. The reason is that a larger discount factor incurs more computation in the policy training process, thus leading to a larger time cost. In this paper, we proposed the new DTWN model based on federated learning and blockchain, and improved the running efficiency of the proposed scheme. We first presented the DTWN model in a wireless edge network consisting of end users and BSs. We further developed a blockchain empowered federated learning scheme in DTWN for realizing edge intelligence. To improve the efficiency of the proposed scheme and better allocate the limited resources, we formulated an optimization problem for given learning accuracy. Specifically, we formulated the problem of edge association between digital twins and BSs and derived an optimal solution to the problem by exploiting the multi-agent reinforcement learning. Numerical results based on the real-world dataset demonstrated that the proposed scheme effectively reduces the learning latency and achieves good learning convergence.


extfieldsofstudy:
Computer Science
Mathematics

text:
Belief Propagation List Ordered Statistics Decoding of Polar Codes

It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.

I. INTRODUCTION
The performance of polar codes [1] under successive cancellation (SC) decoding can be significantly improved by concatenating the polar code with a high rate cyclic redundancy check (CRC) code and using CRC-aided successive cancellation list (CA-SCL) decoding [2]. However, the SCL decoder suffers from high decoding latency due to its serial nature. Various modifications and improvements to SC and SCL have been suggested to address this problem, e.g. [3]- [14].
In [15] it was shown that belief propagation (BP) decoding over the code's factor graph (FG) can be used to improve upon the SC decoder. Efficient implementations, improvements and extensions of BP decoding for polar codes were suggested in [16]- [29]. In particular, it was suggested to implement a BP list (BPL) decoder [23] that applies BP decoding on different permutations of the polar FG layers [30] in parallel. It was also suggested to apply BP decoding over a concatenation of the CRC and polar FGs [21], [25]. Yet, even when combining these ideas, the resulting CRC-aided BPL (CBPL) decoder [25] has a higher error rate compared to CA-SCL.
Another family of decoders for polar codes are based on ordered statistics decoding (OSD) [31]. This approach was used in [32], [33], in which OSD was either applied directly on the channel output, or combined with CA-SCL or SC. Ordered statistics decoding and its box and match variant were also proposed in [34]- [38] for polar and polarlike codes when viewed as a generalized concatenated code [39]. However, the required reprocessing order is typically large. Even though there are known methods for improving the complexity-performance trade-off of OSD [40]- [45], the computational complexity may still be prohibitive.
In the context of OSD decoding of low-density parity-check (LDPC) codes it was suggested [46] to combine BP and OSD decoding by using the soft decoded BP output to rank the code bits rather than using the uncoded information as in plain OSD. In this paper, we start by adapting the approach in [46] to CBPL decoding of polar codes. We apply OSD reprocessing of order one using the soft decoding output of each of the parallel CBP decoders in CBPL. Our simulations show that even OSD with reprocessing order as low as one can significantly decrease the error rate of CBPL, and bring it closer to that of CA-SCL for a relatively small permutation list size. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity. We demonstrate that partial order-2 reprocessing, incorporating only the least reliable half (or even less) of the total number of pairs of most reliable independent bits, results in an error-rate similar to that of full reprocessing.

A. CRC augmented polar codes
Consider the N × N binary matrix: where F ⊗n is the n-fold Kronecker product of the standard polarization kernel F = 1 0 1 1 and n = log 2 N . Denote by A the length K information set of a length N polar code, P(N, K).
Denote the matrix composed of the rows of G N , corresponding to the elements of A, by G N (A). The polar code, P(N, K), is a linear binary block code with generator matrix G N (A) and code dimension K. Encoding a message vector u A of length K with the generator matrix G N (A) (using u A G N (A)) is equivalent to encoding the vector u with generator matrix G N (using uG N ), where u is a vector of length N with message bits u A and with u A c = 0 (i.e., we assume that the frozen bits are all zeros).
Also consider a CRC code which appends r CRC bits to binary vectors of length m. This code can be represented as a linear binary block code with code rate R crc = m/(m + r), a systematic generator matrix G crc of dimensions m × (m + r), and a parity-check matrix (PCM) H crc with r parity check constraints.
For the polar code and CRC code described above, the corresponding CRC-augmented polar code is the linear binary block code of length N , dimension m and generator matrix G aug = G crc G N (A). Note that we set K = m + r, and that the overall code rate is R = m/N .
In our setup, a message word of length m is encoded into a codeword x = (x 1 , . . . , x N ) of length N using G aug , which is then BPSK-modulated and sent across a binary input additive white Gaussian noise channel (BIAWGNC) with noise Z ∼ N (0, N 0 /2), so that the channel output is given by, The log likelihood ratios (LLRs) of the codeword's bits, ch i , based on the respective channel output, y i , are given by for i = 1, . . . , N , where σ 2 = N 0 /2.

B. CRC-aided belief propogation list decoding
In [15] it was suggested to apply BP decoding on the FG representing the encoding with the generator matrix in (1). This FG is shown in Fig. 1. The BP decoder can be implemented in parallel, thus reducing the latency and increasing the throughput of the decoder compared to SC and SCL decoding. The BP uses left and right-propagating messages over the x 4 x 5 x 6 x 7  edges of the FG. Denote by L t i,l (R t i,l , respectively) the leftpropagating (right-propagating) message out of (into) variable node i in the l'th FG layer at iteration t, for 0 ≤ l ≤ n and 1 ≤ i ≤ N . An iteration of BP consists of a right-toleft message propagation, in which messages are sent from the right-most layer of the FG to the left-most layer, followed by a similar left-to-right propagation of messages. The leftmost (right-most, respectively) layer represents the LLRs of the message and frozen bits (codeword bits). The initialization of the messages (at iteration t = 0) is, The detailed iterative message passing equations are provided in [15].
To reduce the error-rate, it was suggested to perform the message passing on the concatenation of the CRC FG, represented by the PCM H crc , and the polar FG. An example is shown in Fig. 1. As stated in [21], for this concatenation to be beneficial in terms of error-rate performance, the messages must first evolve through I thr iterations on the polar FG alone, so that the information layer LLRs will become reliable enough. The BP iterations are performed until either a predetermined maximum number of iterations I max have been reached, or until a certain stopping condition has been met. Following [19], [20], in our implementation we stop iterating if the following two conditions are satisfied. The first condition isx =û · G N whereû andx are the hard-decisions of the information LLRs and codeword LLRs, respectively. The second condition is thatû A satisfies the CRC constraints (û A H T crc = 0). To further reduce the error-rate, we can perform CBP on a list of L layer-permuted polar FGs [22], [23], [30], thus obtaining the CRC-aided BP List (CBPL) decoder [25]. The estimated codeword is the CBP outputx with BPSK representation closest, in Euclidean distance, to the channel output, y, out of all the outputs that are valid codewords (namely, the outputs of the CBP instances in which the stopping condition was met). To simplify the implementation, instead of using different polar FGs in the CBP realizations, we may permute their inputs and outputs [24].

C. Ordered statistics decoding
Ordered statistics decoding (OSD) [31] is a general method for decoding a linear binary block code. Consider a linear binary block code of blocklength N and K information bits transmitted over the BIAWGNC (2). The code is represented by a K ×N full row rank generator matrix, G. The OSD algorithm consists of two main parts [31]: Finding the most reliable independent basis (MRIB) from the columns of G with respect to the values in = ch (computed from the channel output y according to (3)), and a reprocessing stage. The MRIB is a set of K columns from G, which correspond to the indices in that contain the most reliable LLRs (LLRs with highest absolute values) under the constraint that these columns are linearly independent (over GF (2)). The process of finding the MRIB is described in detail in [31]. It starts by sorting the absolute values of the components of in decreasing order. We then apply the same ordering (permutation) on the columns of G. Following that, we use Gaussian elimination conducted on the above mentioned permuted G in order to find the first K positions of linearly independent columns, which serve as the MRIB. In the end of the process, we have a new matrix, G, which is an equivalent representation of the code up to some permutation, λ, of the code bits. The first K columns of G are the MRIB columns of G with respect to . The above mentioned Gaussian elimination is implemented such thatG is represented in a systematic form, i.e.
where I K is the K×K identity matrix, and A is a K×(N −K) matrix. Denote by˜ = λ( ) the permutation of the LLRs vector, , using the same permutation λ. The first K values in˜ (which are the most reliable LLRs) can be used to obtain an initial estimate to the information vectorv = (v 1 , · · · ,v K ) (corresponding to the systematic generator matrixG), by using hard decisions:v for 1 ≤ i ≤ K. We can now start the reprocessing stage of the OSD algorithm. For each 0 ≤ i ≤ q, flip all possible combinations of i bits inv, i.e., considerv ⊕ e (⊕ is the bit-wise XOR operator) for all error patterns e of Hamming weight at most q (the total number of error patterns is q i=0 K i ). For each error pattern, e, re-encodev ⊕ e using G, and calculate the Euclidean distance between the BPSK representation of the resulting codeword and the permuted channel output vector,ỹ = λ(y). Keep track of the distances, so that after all possible error patterns of Hamming weight at most q have been tested, select the (permuted) codeword with minimum distance fromỹ, and inversely permute it by λ −1 to obtain the OSD(q) estimate of the transmitted codeword.

III. INCLUSION OF OSD IN CBPL DECODING
In order to implement OSD decoding efficiently for LDPC codes, it was proposed [46] to determine from the soft output of a preliminary BP decoder, rather than using = ch . This is usually advantageous, since it will make the LLRs in more reliable (more LLRs will have the correct sign).
We assume the setup described in Section II, where a codeword x from a CRC-augmented polar code of length N = 2 n and with generator matrix G aug is transmitted over the BIAWGNC, resulting in a channel output y. Our suggestion for further improving the error performance of CBPL decoding is to perform OSD(q) on the soft output of each of the L CBP instances running in parallel, as depicted in Fig. 2 for q = 1. We denote this decoder with reprocessing order 1 by CBPLOSD (1). Interestingly, as we report later on, even for q = 1 we obtain a substantial improvement on the performance of the CBPL algorithm. On the other hand, plain OSD decoding requires much higher values of q to reach the same performance, with a much higher total number of operations. A further improvement is obtained by using CBPLOSD(2). This is considered in Section IV. x (2) x(L) Fig. 2. The CBPLOSD(1) scheme. The permutation set is S = {π j } L j=1 , and CBP(π j ) denotes CBP with a polar FG layer permutation π j .
In Fig. 2, the channel output y is the input to L parallel CBP decoders with different polar FG layer permutations. After meeting the stopping criterion (from section II-B) or completing the maximum number of iterations, I max , in the j-th CBP decoder, j = 1, . . . , L, we apply OSD(1) decoding using its soft output LLR vector, (j), which contains the decoded LLRs of the codeword bits. The OSD(1) routine at the j'th branch, uses this soft output, along with y and G aug as input, and outputs a codeword estimatex(j). Note that an output of OSD is always a valid codeword. Thus, we simply choose the codeword estimate,x(f ), with BPSK representation closest to y as the final output of the decoder, The reprocessing part of the OSD(1) decoder can be implemented efficiently as follows. Denote byG aug the permuted systematic generator matrix obtained from G aug in the first stage of OSD described above (finding the MRIB). Denotê v 0 ∆ =v wherev is obtained from the LLRs of the bits corresponding to the MRIB as in (4). Also, is the information vector after flipping the i'th bit inv. The corresponding (permuted) codeword iŝ Denote by g 0 ∆ = (0, . . . , 0), and by g i , the i'th row ofG aug , i = 1, . . . , K. In order to calculatex i for each 0 ≤ i ≤ K efficiently, we can use the relation Furthermore, it can be easily verified that The decoder outputs λ −1 (x i0 ). Using the right-hand-side (RHS) of (5), the reprocessing, which can be implemented in parallel, requires (N − 1)(K + 1) additions / subtractions. The Gaussian elimination over GF(2) required in the first stage of OSD can also be implemented in parallel in hardware [47].
IV. PARTIAL HIGHER ORDER OSD REPROCESSING So far we have focused on CBPLOSD(1), as it has the lowest computational complexity. Yet, a lower error rate may be achieved by using CBPLOSD(q) for q > 1. In this section, we propose approximating higher order reprocessing by performing it only on the bits that are associated with the least reliable LLRs. We demonstrate this approximation for CBPLOSD (2), and show that it can be used to achieve almost the same performance as that of regular CBPLOSD(2), while cutting back half or more of the reprocessing complexity.
Recall the information vectorv from (4) and the systematic K × N generator matrixG =G aug , where g i denotes its i'th row. Also recall the vector s from (5). Let us further denote byv (i,j) the resulting information vector after flipping the i'th and j'th bits inv, and its corresponding codeword bŷ The main bottleneck of order-2 reprocessing is the search for the codewordx (i,j) with BPSK closest to the permuted channel outputỹ in terms of Euclidean distance, To determine the final OSD(2) estimate, the result of the search (6) needs to be compared to the OSD(1) estimate in (5) by minimum Euclidean distance toỹ. In (6) we search over K 2 = [K(K − 1)]/2 pairs of indices (i, j). Similarly to (5), we have the following relation, Using the RHS of (7), the complexity of this search, and thus of order-2 reprocessing, is about N K 2 /2 additions. The RHS of (7) can be expressed using matrix multiplication (that only requires additions / subtractions, and can be implemented efficiently in parallel) as follows. First define a K × N matrix A such that the i'th row, i = 1, . . . , K, of A is s · (−1) g i (element-wise multiplication and exponentiation). Next, define an N × K matrix B such that the j'th column, j = 1, . . . , K, of B is (−1) g j . Finally define the K × K matrix C by Then the RHS of (7) can be written as A similar formulation using matrix multiplication applies to the partial reprocessing method that we now suggest. Recall the permuted LLRs (˜ 1 , . . . ,˜ K ), corresponding to the MRIB, defined in Section II-C. To reduce the complexity we propose the following approximation to the search in (7). For any integer M < [K(K − 1)]/2, we perform this search only on the M pairs of indices (i, j) with the lowest values of |˜ i | + |˜ j |. Namely, we flip the M pairs of bits inv which are associated with the least reliable LLRs (LLRs with the lowest absolute values), and enumerate the M resulting codewords using the RHS of (7). Since |˜ i | > |˜ j | for 1 ≤ i < j ≤ K, this is implemented by enumerating over the indices (i, j) during reprocessing in the following decreasing order: i = K −1, K −2, . . . in the outer loop and j = K, K −1, . . . , i+1 in the inner loop, until we have exhausted M such pairs. This approximation can be straightforwardly extended for higher orders. In the case of order 2, it reduces the complexity of the search over the pairs from about N K 2 /2 to about N M .

V. SIMULATION RESULTS
In this section we present decoding results for two CRCaugmented polar codes of rate R = 0.5 with blocklengths N = 256 and N = 512. The CRC generator polynomial for both codes is the 5G standardized 6-bit polynomial g 6 (x) = x 6 +x 5 +1. All the CBP decoders were set to use I max = 100, I thr = 50, and a total of L = 6 such decoders for CBPL were used, with their input / layer permutations corresponding to all the 3! = 6 possible permutations of the 3 right-most layers of the polar FG. The CA-SCL list size was also 6.
A. CBPOSD(1) and CBPLOSD (1) In Fig. 3 we compare the performances of plain OSD, CBP, CBPOSD(1), CBPL, CBPLOSD(1) and CA-SCL for the code with blocklength N = 256. In Fig. 4 we repeat this comparison for the other code with N = 512. As can be seen, in the high SNR range, the gain in E b /N 0 attributed to the inclusion of OSD(1) in CBPL is around 0.5dB for the N = 256 code and 0.4dB for the N = 512 code. When no permutations are used (L = 1), incorporating OSD(1) in CBP provides a 0.3dB gain in the high SNR range for both codes. Both figures demonstrate that even for a relatively small permutation list size (L = 6), the performance of CBPOSD(1) comes close to that of CA-SCL with a similar list size. On the other hand, plain OSD requires a much larger reprocessing order to match the performances of CBPLOSD(1) and CA-SCL.

B. Partial order-2 reprocessing
In Fig. 5 we compare plain CBPLOSD(2), in terms of error performance, to CBPLOSD decoders in which the search in (7) was conducted only on a portion of the least reliable bits, using the CRC-augmented polar code with blocklength N = 256. We refer to the CBPLOSD decoder in which the partial order 2 reprocessing takes into account only α · RN 2 of the least reliable pairs (0 < α < 1) by P-CBPLOSD(2, α).
We notice that CBPLOSD (2) shows a gain of about 0.2-0.3dB in E b /N 0 over CBPLOSD(1) in the simulated range. For the decoders with partial reprocessing, even when we go over only 1/8 of the least reliable pairs (and, as a result, reduce the decoding complexity by about 8), the performance degradation, compared to full order-2 reprocessing, is about 0.1dB or less in this example. This degradation can be mitigated by a small amount by going over 1/4 or 1/2 of the least reliable pairs instead, and the resulting performance comes close to that of full order-2 reprocessing.
Similar observations can be seen in Fig. 6 for the second code with N = 512.

VI. CONCLUSIONS
We have shown how to combine OSD with CBPL decoding of polar codes. Even when the reprocessing order of the OSD was as low as one, the new decoder was shown to improve on CBPL in terms of the error performance by 0.4-0.5dB in the high SNR region, for the two CRC-augmented polar codes considered. Additional gain can be obtained by increasing the OSD reprocessing order to two. Partial reprocessing, carried out only on the least reliable belief propagation decoded pairs of MRIB bits, can reduce the computational complexity of plain order-2 reprocessing by a significant amount, at the expense of a relatively small performance degradation.