# On Security Weaknesses and Vulnerabilities in Deep Learning Systems

Zhongzheng Lai  Huaming Chen1  Ruoxi Sun  Yu Zhang  Minhui Xue  Dong Yuan1
Zhongzheng Lai, Huaming Chen, Yu Zhang and Dong Yuan are with the School of
Electrical and Computer Engineering, The University of SydneyRuoxi Sun and
Minhui Xue are with CSIRO’s Data61, Australia1Corresponding author.

###### Abstract

The security guarantee of AI-enabled software systems (particularly using deep
learning techniques as a functional core) is pivotal against the adversarial
attacks exploiting software vulnerabilities. However, little attention has
been paid to a systematic investigation of vulnerabilities in such systems. A
common situation learned from the open source software community is that deep
learning engineers frequently integrate off-the-shelf or open-source learning
frameworks into their ecosystems. In this work, we specifically look into deep
learning (DL) framework and perform the first systematic study of
vulnerabilities in DL systems through a comprehensive analysis of identified
vulnerabilities from Common Vulnerabilities and Exposures (CVE) and open-
source DL tools, including TensorFlow, Caffe, OpenCV, Keras, and PyTorch. We
propose a two-stream data analysis framework to explore vulnerability patterns
from various databases. We investigate the unique DL frameworks and libraries
development ecosystems that appear to be decentralized and fragmented. By
revisiting the Common Weakness Enumeration (CWE) List, which provides the
traditional software vulnerability related practices, we observed that it is
more challenging to detect and fix the vulnerabilities throughout the DL
systems lifecycle. Moreover, we conducted a large-scale empirical study of
3,049 DL vulnerabilities to better understand the patterns of vulnerability
and the challenges in fixing them. We have released the full replication
package at https://github.com/codelzz/Vulnerabilities4DLSystem. We anticipate
that our study can advance the development of secure DL systems.

###### Index Terms:

Security Weaknesses, Vulnerabilities, AI system.

##  I Introduction

The deep learning (DL) development has greatly advanced its application in
different domains, including computer vision, natural language, and signal
processing. It has now emerged as one of the most promising approaches to
offer cutting-edge inference capabilities by learning and mining latent
relationships from complex data sources. Recent applications develop DL
algorithms to solve complex scientific problems, such as building advanced
recommendation systems for business demands and enhancing intelligent cyber-
physical systems for industry needs. Although it is recognized that current
software development practices have yet to meet the dynamics development
challenges of such systems, software engineers are facing a more challenging
situation in accurately and securely developing such systems.

One tangible cause is the unique data-driven programming paradigm of AI-
enabled systems, which requires complete and accurate understanding and
translation of the functional and non-functional requirements from data to
models and the deployment ecosystems. During the process, enormous research
and development efforts have been devoted to the development of DL frameworks
and libraries. The widely adopted DL libraries have made the integration of DL
models and software systems much easier, and thus greatly facilitate the
system development. Compared to the software engineering practice that has
been extensively investigated [1, 2, 3, 4, 5], an insufficient understanding
of security weakness in DL systems, however, would result in severe
consequences once exploits occur in safety-critical systems, such as aircraft
flight control and autonomous driving systems [6].

Figure 1: Trend of cybersecurity vulnerabilities in TensorFlow.

Previous work addressing issues in DL-enabled systems has focused on multi-
fold aspects, including the usage of machine learning API [7, 8], determining
and categorizing the bugs in DL software [9, 10, 11, 12, 13], and testing the
DL libraries and programs [14, 15, 16]. However, due to limited vulnerability
analysis resources, vulnerabilities in DL systems were much less explored in
the literature than in common vulnerability analysis (such as Android system
vulnerabilities [17]). Figure 1 shows the trend of disclosed cybersecurity
vulnerabilities in TensorFlow [18], a main-stream DL framework, in which the
number of vulnerabilities is increasing dramatically from 34 in 2020 to 243 in
2021, and now 407 till Jan 10th 2023. Such an exponential growth in the number
of vulnerabilities is unprecedented, which motivates us to further investigate
software vulnerabilities in DL systems.

Although identified vulnerabilities have become overwhelming, especially in
the National Vulnerability Database (NVD) with expert-verified Common
Vulnerabilities and Exposures (CVE) ID, our aim is to investigate
vulnerabilities in DL systems. To achieve this goal, we select the five most
popular DL frameworks which are actively maintained, including TensorFlow
[18], Caffe [19], OpenCV [20], PyTorch [21] and Keras [22]. The reason that we
chose multi-DL open source projects rather than focusing on a particular one
is to cover DL systems as broad as possible. While only TensorFlow maintains
the Security Advisory in the official project, this study has expanded the
scope of the investigation with widely deployed rule-based methods for
vulnerability detection from relevant projects.

Specifically, we focus on vulnerabilities with open source code available and
developer discussions across project repositories. These repositories give us
full access to study vulnerabilities in terms of description, location, and
patch. We conclude the results and findings as the contributions in the
following list:

  * •

We conduct the first systematic study of vulnerabilities in DL systems through
manual analysis of 3,049 vulnerabilities from over 10,360 changes
(commits/pull requests) and 443 official CVEs in five DL open-source
frameworks.

  * •

We provide an analysis of the root causes and symptoms of vulnerabilities,
resulting in a classification that could benefit future research on the
analysis of DL vulnerabilities.

  * •

We discuss the challenges in detecting and fixing vulnerabilities in DL
systems and suggest future research directions to advance the detection and
patching of DL vulnerability.

  * •

We open-source the source code, datasets, and analysis results as a public
replication package for software security researchers and practitioners, which
can be found at [23].

##  II Background and Related Work

###  II-A Background and Motivation

It is widely acknowledged that DL has enhanced a growing number of areas, such
as scientific research and industry application, with intelligent capability.
Potential areas have seen efficient data-driven solutions including self-
driving cars [24], fraud news detection [25] and visual recognition [26].
However, the development of such a DL-enabled system requires dedicated
efforts from all stakeholders, including, but not limited to, problem
definition, requirement analysis, and model development [27, 28, 3, 29, 30].
In most cases, it will be even difficult for developers to implement a DL
program from scratch since a decent mathematical foundation will be required
[8]. Another challenge is the tedious multistage for developing DL-enabled
systems [31, 32]. Thus, enormous efforts from academia and industry have been
dedicated to supporting and facilitating the development process, such as
recently emerging infrastructure frameworks and services [18, 21, 19, 22, 33,
34].

While the successful deployment of an intelligent system is critical, recent
research also evaluates DL systems in terms of its security and privacy [35,
36, 37, 38, 39, 40]. One important category of security threats for DL systems
is introduced by infrastructure frameworks, such as TensorFlow and PyTorch
[8]. Such frameworks are generally designed to offer off-the-shelf solutions
and access to specific computational resources with high-level APIs. However,
a first reported vulnerability related to DL systems is identified as
CVE-2018-5268 in NVD. It can exploit the Microsoft Cognitive Toolkit (CNTK) by
launching remote attacks for a total loss of Confidentiality, Integrity and
Availability (CIA) of the system without required authentication [41, 42].
Taking TensorFlow as an example in Figure 1, the number of official
vulnerabilities in NVD has greatly increased since 2021, with a total of 407.
This indicates that the critical security risks in DL systems are expanding
dramatically. It remains limbo for an in-depth and practical understanding to
incorporate the knowledge from NVD, especially with the well-defined Common
Weakness Enumeration (CWE) list research concept.

In this work, we anticipate for a large-scale systematic investigation of the
vulnerabilities in DL systems with up-to-date CWE tools, particularly for DL
infrastructure frameworks, to understand their root causes, symptoms, and
fixed pattern directly related to the specific DL system characteristics.
Further actionable implications for all practitioners and researchers are
provided with manual efforts of analysis for the unique and reliable
resources, such as source code, developer analysis and discussion, and so on.
The following sections will convey the details of the methodology and the data
analysis process. To highlight the critical value of our work compared to
other most recent studies, Filus  _et al._ [43]initially attempts to explore
104 CVE instances related to memory operations in Tensorflow. However, only
six different CWE types are concluded as findings, which limits its general
applicability for vulnerability analysis and the specific implication for the
development of secured AI-enabled software systems. Another recent work [44]
has an emphasis on research on attack and defensive approaches for DL
frameworks.

###  II-B Related Work

It is a hot topic to practically understand the process of AI-enabled system
development, particularly with advanced DL techniques. In addition to the work
in Sec. II-A, two directions are related to our works, namely empirical study
of AI-enabled systems, and testing on AI-enabled systems.

An Empirical Study of AI-enabled Systems.  For the empirical study of AI-
enabled systems, we mainly discuss the existing works on identifying the
latent bugs and faults for the development and deployment of such systems. It
should be noted that many research challenges in relation to AI-enabled
systems from the perspective of software engineering may have focused on
engineering requirement analysis and the semantic development framework. We
limit the related works here for bugs and faults related empirical analysis.

The work by Thung _et al._ [45] studied three different machine learning-based
systems, including Apache Mahout, Lucene, and OpenNLP. General bugs for
machine learning-based systems were surveyed with the proposed category,
severity, and impact of the bug.Zhang _et al._ [46] conducted a comprehensive
survey covering 144 papers on bug testing in machine learning-based systems.
Zhang _et al._ [47] further explored the bugs in TensorFlow-built DL
applications. In total, 175 TensorFlow application bugs were collected from
Stack Overflow QA pages and GitHub.

In [9], the focus was on bugs in software that use DL libraries, while some
empirical studies are subject to specific types of bugs, such as performance
bugs, numerical bugs, and tensor shape faults [10, 11, 12, 13, 5, 48].

Testing on AI-enabled Systems.  In order to identify and evaluate the general
bugs and faults in AI-enabled systems, software testing is one prominent
technique. One identified challenge for testing on AI-enabled systems is
defining the test oracle for the implementation of machine learning
classification algorithms [49, 14]. Differential testing has also been applied
to test DL libraries, such as CRADLE in [15]. The test of DL libraries by
generating effective DL models through guided mutation is proposed as LEMON
(DL Library tEsting via guided MutatiON) in [16]. Christou _et al._ [50]
proposed IvySyn to automatically detect DL kernel code implementations,
introduce fuzzing hooks for type-aware mutation-based fuzzing, and synthesize
code that propagates offending inputs for vulnerability testing. Other works
have considered the testing for DL from different aspects, such as
prioritizing inputs [51], testing for DL operators [52, 53].

TABLE I: Statistics of the studied deep learning frameworks in our study

Framework | GitHub Stars | Commits | Pull Requests |  SLOC* (C/C++) | SLOC (Python) | Closed Issues | Vulnerabilities
---|---|---|---|---|---|---|---
TensorFlow | 171.0k | 149,895 | 22,484 | 2,263,966 | 687,408 | 34,434 | 2,154
PyTorch | 62.0k | 137,429 | 62,215 | 1,207,216 | 780,704 | 20,730 | 217
OpenCV | 66.1k | 33,142 | 13,625 | 1,372,158 | 35,501 | 7,135 | 563
Keras | 57.2k | 7,886 | 5,831 | 0 | 194,240 | 11,325 | 45
Caffe | 33.1k | 12,633 | 2,240 | 61,299 | 5,379 | 3,891 | 70

  * *

SLOC: source lines of code.

###  II-C Vulnerability Management Related Database

Common Weakness Enumeration (CWE) [54], Common Vulnerabilities and Exposures
(CVE) [55], and National Vulnerability Database (NVD) [56] are the three
important databases that standardize the way vulnerabilities are identified,
described, and addressed. CWE [54] is a list that contains a comprehensive
classification taxonomy to identify and describe weaknesses in software and
hardware systems. It focus on abstract descriptions of common weaknesses,
which attempt to capture the root causes that lead to security problems. CVE
[55] aims to identify, define, and catalog vulnerabilities. For each record,
CVE provides a unique ID and a consistent description to ensure that
professionals discuss and work on the same issues. NVD [56] is supplementary
of CVE which provides enhanced information about vulnerability, including
severity scores and patch availability. It collects and analyze the public
available information related to each CVE and provides richer information to
help professionals better understand and evaluate the issues.

##  III Methodology

In this section, we outline the open-source data collection and analysis
methods used in this work, covering the five most popular DL frameworks
(TensorFlow, Caffe, OpenCV, PyTorch and Keras). We curate, process, and
analyze the data with cross-reference checking from multiple sources,
including GitHub repositories and NVD. The ultimate goal is to ensure that we
have obtained a high-quality dataset to characterize and investigate
vulnerabilities in the context of DL systems, along with the latest
definitions of vulnerabilities in the CWE List version 4.9 [54].

###  III-A Vulnerability Dataset Establishment

In this section, we introduce our method for collecting vulnerability
datasets, aiming to comprehensively identify all vulnerabilities in line with
all possible software security related issues. Figure 2 shows a two-stream
method obtains high-fidelity vulnerabilities in a multi-round process with a
well-designed reference checking support among public CVEs, GitHub pull
requests, issue reports, and commit logs.

Data collection.  In particular, one stream focuses on NVD, while another
stream targets GitHub. In order to automatically identify vulnerabilities from
GitHub repositories, we design a comprehensive set of regular expression rules
derived from the existing works [57, 58]. To ensure the quality and
effectiveness of the search keywords, we followed a four-step empirical
approach as described below:

  * •

Initial keyword set building. We combine the vulnerability search keywords
from [57] with the regular expression from [58], establishing an initial set
of keywords.

  * •

Pilot validation. We use the TensorFlow official “Security Advisory” records
as the validation set to evaluate the effectiveness of the initial set of
keywords.

  * •

Manual optimization. We manually analyzed the false negative results which
cannot be identified by previous keywords searching and optimized the keywords
to boost the detection rate on the validation set.

  * •

Optimization during manual investigation. We then applied the search keywords
from previous step to all five GitHub repositories to scan the latent
vulnerabilities. During the manual investigation of the scanning results, we
further optimized the search keywords based on false positive records to
minimize the false detection rate.

Figure 2: An overview of proposed two-stream data analysis framework.

The final keywords are listed in Table II. Note that in some projects, such as
Caffe and Keras, there is no expressive vulnerability update information. To
resolve this problem, a comprehensive set of latent vulnerability detection
keywords is built and optimized accordingly, to scan GitHub resources. To
date, all commits, issues, and pull requests of the five DL frameworks that
are created on or before January 10, 2023 are obtained with GitHub APIs, which
are further input to our initial taxonomy analysis of vulnerabilities in DL
systems. The initial statistics of the studied DL models are reported in Table
I.

Screening.  Following selection criteria are defined for dataset collection:
(i) Mining established database - the vulnerability is reported in two major
websites, including GitHub security advisory [59] and National Vulnerability
Database [56]; (ii) Mining actively updated repositories - the vulnerability
could be identified and fixed prior to be reported to NVD, which normally
takes weeks or months for verification. Since the data in GitHub repositories
could be noisy, several sub-rules are defined for preprocessing:

  * •

We only collect merged PR where all changes are approved and accepted.
Therefore, such discussion and detailed information will be available and are
helpful for vulnerability classification and understanding.

  * •

We collect PRs that match the regex rules in Table II.We generate a
comprehensive set of regular expression rules based on the search keywords
obtained through manual optimization (refer to the four-step approach).

  * •

There is an available patch to fix the identified security-related commits.
The patch normally contains developers’ comments and the code for fixing,
allowing to understand the root cause of vulnerability easily, providing
information of code changes for the fixing patterns and efforts.

TABLE II: The regular expression for vulnerability search

Vulnerability Type |  Keywords |  Regular Expression
---|---|---
Common |  Security, Safety, Vulnerability, Threat, Violate, Malicious |  (in)?secur(e$\mid$ity)$\mid$unsafe$\mid$safer$\mid$vuln$\mid$threat$\mid$violate$\mid$malicious
Symptom |  Abort, Core Dump, Crash, Fatal, Segmentation Fault, Check Fail, Undefined Behavior |  abort$\mid$core.dump$\mid$crash$\mid$fatal$\mid$seg(ment)?(ation)?(.)?fault$\mid$check.fail$\mid$fail(ing$\mid$-ed)?(.)?check$\mid$assertion.fail$\mid$undefined.behavio(u)?r$\mid$misbehave
Attack Method |  Attack, Code Injection, Poison, Remote Code Execution, Arbitrary Code Execution, Denial of Service |  attack$\mid$code.injection$\mid$poison$\mid$(remote$\mid$arbitrary).code.execution$\mid$\brce\b$\mid$-denial.of.service$\mid$\bdos\b
Vulnerability Database |  CWE, CVE |  \bcve\b$\mid$\bcwe\b
Permission |  Authentication, Unauthorised Access, Permission |  unauthenticated$\mid$gain.access$\mid$permission
Numeric |  Divide by Zero, Integer Overflow, Integer Underflow, Integer Truncation, Floating Point Exception |  div(i(de$\mid$sion)(s)?)?.by.(zero$\mid$0)$\mid$int(eger)?.(overflow$\mid$underflow)$\mid$int(eger)?.-truncation$\mid$floating.point.exception$\mid$\bfpe\b
Memory |  Out of Memory, Memory Leak, Memory Corruption, Invalid Memory Access, Arbitrary Memory Access, Heap Overflow, Stack Overflow, Out-of-Bounds (Access/Read/Write), Overflow, Overrun |  out(side)?.of.memory$\mid$\boom\b$\mid$(data$\mid$memory).(leak$\mid$corruption)$\mid$invalid.-memory.access$\mid$access.(\w+.)?invalid.memory$\mid$write.(\w+.)?immutable.-memory$\mid$access.(\w+.)?undefined.memory$\mid$arbitrary.memory.(read$\mid$write-$\mid$access)$\mid$heap.(buffer.)?overflow$\mid$stack.overflow$\mid$out(side)?.of.bound(s)?$\mid$-\boob\b$\mid$overflow$\mid$overrun
Resource Management |  Use After Free, Use of Uninitialized Resource |  use.after.free$\mid$uninitiali[s$\mid$z]ed
Pointer |  Null Pointer Dereference, Null Pointer Exception, Reference Binding to Null Pointer |  null(.)?(pointer$\mid$ptr)?(.)?(deref(erence)?$\mid$exception)$\mid$deref(erenc(e$\mid$ing))?.of.-null(.)?(pointer$\mid$ptr)?$\mid$\bnpe\b$\mid$reference.binding.to.null(.)?(pointer$\mid$ptr)?
Data Validation |  Validation |  \bvalidat(e$\mid$ion)(d$\mid$s)?\b
Other |  Dead Code, Race Condition, Format String, Type Confusion, Shape Check |  dead(.)?code$\mid$\brac(e$\mid$ing)$\mid$thread.safe$\mid$format.string$\mid$string.format$\mid$type.-confusion$\mid$shape.check$\mid$check.shape

Implementation.  Specifically, to reduce the data harvest effort, we implement
a data acquisition system to automate the data collection process, as
illustrated in Figure 2. This process involves five datasets: NVD, GitHub,
Raw, Distilled, and Manual. The NVD dataset houses official CVE records,
offering professional vulnerability descriptions. The GitHub dataset comprises
code, commits, pull requests, and issues from DL projects. The Raw dataset
collects unprocessed data directly crawled from GitHub, while the Distilled
dataset retains data that have been automatically filtered or processed.
Finally, the Manual dataset is dedicated to data that have been processed
manually.

For public vulnerability data, we implement a NVD Crawler to query the CVE
records by DL framework name from NVD. In addition, for TensorFlow, which
includes well-maintained security advisories, we implement TFSecurityAdvisory
Parser to extract useful information from security advisory files, such as
title, CVE Number, patches (the patching approaches), issue description,
impact (the symptom or consequence), vulnerable versions, mitigation, credits,
attribution. These data will be used as a reference to improve the performance
of our latent vulnerability detection keywords.

For latent vulnerability data, we clone the five repositories on the local
machine and execute GH Filter, which integrates with the GitHub CLI command to
extract all pull requests, commits and issues. Only a simplified version of
the logs is returned. We then use GHCrawler (PR) to query the GitHub REST API
and harvest completed pull request information. Then, we applied a latent
vulnerability search on the pull request records to expose those vulnerability
patches. Finally, GHCrawler (Commit) will crawl the completed commit
information for the corresponding vulnerability patches.

###  III-B Classification and Labeling Process

In order to effectively characterize the vulnerabilities in DL systems, we
focus on three distinguished aspects, _i.e._ the root causes, the identified
symptoms, and the patching process of vulnerabilities, by following the widely
adopted open coding procedure [60]. The data is specifically curated with
‘impact’ and ‘patches’ information. Meanwhile, we performed an iterative
manual labeling process involving the authors’ efforts to substantially
investigate the identified latent vulnerabilities with their expertise and
development knowledge. The iterations are as follows:

Iteration 1. First we create the initial search pattern following [57, 58].
Official vulnerabilities are used to improve the detection performance of
search keywords. The search patterns are iteratively improved and achieved the
best detection results (_e.g._ false negatives and positives). Optimal search
patterns are applied to the three sources (_i.e._ PRs, commits, and issues) of
data for latent vulnerability detection. Specifically, we apply latent search
for PR, and then according to the vulnerable PR results, find the
corresponding commits and Issues. Within this iteration, an initial version of
classification and labeling strategy is obtained, according to the search
patterns and a preliminary discussion.

TABLE III: Latent vulnerabilities identified in Iteration 1.

Framework | NVD Data | Pull Requests | Commits
---|---|---|---
TensorFlow | 407 | 1,950 | 3,072
PyTorch | 1 | 286 | 930
OpenCV | 35 | 735 | 2,137
Keras | 0 | 97 | 373
Caffe | 0 | 96 | 241

Iteration 2. For detection results from Iteration 1, two authors manually
review PRs, commits, and issues, including source code, title, description,
comments, and discussion. After review, authors independently label records
from seven aspects according to the review of CWE List 4.9 from the research
concept: (1) taxonomy, (2) CWE ID, (3) root cause, (4) fixing pattern, (5)
symptoms, and whether it is a (6) vulnerability and (7) DL-related. As this
paper mainly focuses on DL-related vulnerability, the taxonomy was further
broken down into DL-specific taxonomy. The results were then compared, and the
two authors have demonstrated an almost perfect agreement by achieving a Kappa
coefficient of 0.895 [61]. For the disagreements in the labels, a discussion
was conducted to revise the classification and labeling strategy accordingly.

Iteration 3. Two authors thoroughly reviewed all data with the revised
strategy again, and had a comparative discussion of the outcome, including all
disagreements regarding all seven aspects. Eventually, a final agreement on
the taxonomy of the root causes is reached by resolving all disagreements.

###  III-C Research Questions

To ensure that the study comprehensively analyzes the identified
vulnerabilities, we answer the following research questions that are concerned
with the root causes of vulnerabilities in DL systems and challenges for
patching the vulnerabilities:

  * RQ1:

What are the common root causes of DL-specific vulnerabilities in the DL
frameworks?

  * RQ2:

What are the challenges in detecting vulnerabilities?

  * RQ3:

In terms of fixing the vulnerabilities, what are the main challenges, and how
to address them?

It is expected to understand how vulnerabilities in DL systems arise by
studying RQ1. The summary of common root causes will support the answers to
RQ2 and RQ3 by providing more accurate explanations. Moreover, new challenges
imposed by the key differences between DL systems and traditional software are
investigated.

##  IV Experimental Results

In this section, we present the experimental results. We have reviewed the
latest CWE List report and categorize the vulnerability for its most relevant
software weakness types, which is illustrated in Table IV. Overall, 72
different types of vulnerabilities from CWE List 4.9 are identified. However,
still near 9% of the vulnerabilities could not be well aligned with the
current CWE frameworks.

TABLE IV: The vulnerability types based on CWE version 4.9 from analytic data

Pillar ID | CWE Pillar | CWE Class/Base in Deep Learning Systems | Proportion
---|---|---|---
CWE-664 | Improper Control of a Resource Through its Lifetime | CWE-22, CWE-94, CWE-118, CWE-119, CWE-120, CWE-125, … | 33/418
CWE-682 | Incorrect Calculation | CWE-131, CWE-190, CWE-191, CWE-193, CWE-369, CWE-1339 | 6/13
CWE-691 | Insufficient Control Flow Management | CWE-248, CWE-362, CWE-431, CWE-617, CWE-670, CWE-674,… | 9/94
CWE-693 | Protection Mechanism Failure | CWE-354, CWE-778, CWE-311 | 3/101
CWE-703 | Improper Check or Handling of Exceptional Conditions | CWE-237, CWE-241, CWE-252, CWE-280, CWE-754, CWE-755 | 6/59
CWE-707 | Improper Neutralization | CWE-20, CWE-77, CWE-1284, CWE-1285, CWE-1287 | 5/149
CWE-710 | Improper Adherence to Coding Standards | CWE-476, CWE-561, CWE-1357 | 3/198

###  IV-A RQ1: Root Causes of Vulnerabilities

As an immediate outcome of the classification and labeling process from
Section III-B, the root cause of the 3,049 vulnerabilities in DL systems are
categorized into 7 groups, as detailed below.

Root cause 1: Insufficient computational resource control.  A sufficient
control level of resources is not maintained throughout the development
lifetime. In DL systems, computational resources are substantial, which
requires the software to strictly follow the instructions to create, use and
destroy the resources, including the tensor, memory, and pointer. Among the
950 resource control related vulnerabilities, the subjects are diverse and the
operations are different, making the developers stuck in a difficult situation
and hard to handle the resources correctly. We have identified the following
vulnerability subsets of root cause 1:

  * •

Improper resource validation. Due to excessive usage of high-performance
computational resources, developers need to properly validate the incorporated
resources and the elements defined in the code, including GPU availability,
algorithm parameters, tensor shape, rank, and dimension. A classical issue
related to tensor shape is found in CVE-2021-37676 in Figure 3, in which
inference of tensor shape does not validate the input, leading to attacks
exploiting unexpected privileges to launch undefined model behavior.

  * •

Incorrect resource usage. The developers need a proper definition of the
operation to the resources, in which of the DL-enabled systems the major
concerns are from the data and memory buffer. Handling data type differences
and conversion could be an even worse problem when dealing with GPU kernel. A
heap buffer overflow vulnerability is CVE-2019-16778 in TensorFlow, which
represents a typical example of incorrect type conversion from int64 to int32.
Similarly to the out-of-bounds memory access issue, operations within the
memory buffer bounds require proper restriction to prevent memory overflow,
corruption, and invalid array write. In particular, the tensor is a key
element in DL. Thus, giving explicit instructions on resource usage is
critical.

  * •

Uncontrolled resource release. The excessive range of resources for DL have
brought developers a new landscape of managing resource after use. In addition
to the weakness of ‘Double Free’, ‘Use After Free’ becomes common for the data
input usage, such as the malicious behavior when decoding PNG images in
CVE-2022-23584.

Figure 3: Example of CVE-2021-37676 for resource control.

Improper resource validation, incorrect resource usage, and uncontrolled
resource release are the root causes of vulnerabilities due to insufficient
computational resource control.

Root cause 2: Incorrect security-critical gradient calculation&operation.  If
security-critical calculation is not performed correctly, it could potentially
lead to incorrect resources allocation and incorrect privileges assignment. In
DL, massive gradient calculations are required for the learning and inference
capability. Since the calculation is sensitive to both training and testing
stages, developers are prone to ignore the issues, which will sometimes be
hard to fix. Two major types are among the 418 calculation caused
vulnerabilities:

  * •

Wrong calculation. Developers may ignore the validity of the calculation
throughout DL development, leading to vulnerabilities such as ‘Divide by
Zero’, ‘Incorrect Calculation’, and ‘Incorrect Calculation of Buffer Size’,
according to CWE List version 4.9. Gradient computation is common in DL since
the standard deviation computation can sometimes be numerically unstable. In
Keras issue #2960, the output is rewritten to avoid a division by zero in
BatchNormalization layer. Figure 4 demonstrates the fix for the issue.

  * •

Integer underflow/overflow. Incrementally adding or subtracting a value from
another may cause integer overflow or underflow, respectively. In OpenCV,
there can be serious security issues of remote code execution or denial of
service when loading images remotely, such as CVE-2017-12864.

Wrong calculation, and integer underflow/overflow are the root causes of
vulnerabilities due to incorrect security-critical gradient
calculation&operation.

Figure 4: An example of fixing incorrect gradient computation in Keras issue
#2960.

Root cause 3: Insufficient control flow management in parallel computation.
There is no dedicated code implementation that provides sufficient control
flow management during execution, resulting in security weakness to alter the
control flow. Developing DL systems often involves parallel computing using
shared GPU, threads, and memory. Compared to traditional software systems, DL
systems are more prone to control flow management vulnerabilities. In total,
112 vulnerabilities are identified and categorized into two subsets:

  * •

Unexpected behavior. To better support parallel computing for DL, developers
need to consider the race condition carefully, which could occur in the GPU
fill function (_e.g._ PR#10298 in TensorFlow [62]) and model generators
(_e.g._ PR#5049 in Keras [63]). Such unexpected behaviors will cause the
output to be non-deterministic as well as crash with ValueError. To fix,
developers can either fix the control flow or synchronization, or add
dedicated management checkers for the index.

  * •

Missing handling exceptions. Since exceptions are generally an opportunity for
the run-time test, the developers will add handlers to catch and handle the
exceptions. For DL, there will be many defined blocks that implement
functions, such as OpenMP parallel blocks. A typical example is raised in
PR#4857 in PyTorch [64], which does not allow throwing exceptions across
OpenMP constructs.

Unexpected behavior, and missing handling exceptions are the root causes of
vulnerabilities due to insufficient control flow management in parallel
computation.

Root cause 4: Lack of protection mechanism.  For adversarial attacks, the root
cause of such vulnerabilities is due to unable to provide sufficient defense.
A ‘missing’ protection mechanism is particularly prevalent in DL. One typical
example is GPU operation that reads invalid memory, causing the ‘Insufficient
Verification of Data Authenticity’ in CVE-2021-41203. Providing Checkingpoints
loading the infrastructure is demanded.

Lack of protection mechanism is a prevalent vulnerability in DL.

Root cause 5: Improper DL corner case handling.  During normal operation, it
is desired to consider handling exceptional conditions. DL encapsulates more
input and output variables, return value, and run-time model state. Thus, how
to deal with more corner cases is difficult for DL systems. In PR#7071 in
Keras [65], a simple but effective example is related to the values of the
data label. The patch adds one more condition to check the label values.
Figure 5 shows PR#1048 in Caffe [66] where a code snippet fixes the
exceptional condition of setting the weight pointer as NULL for convolutional
layer training. For exceptional conditions, as we can see from the code
snippets, PR#1048 [66] and PR#7071 [65] have no common variables, and
vulnerabilities are hard to identify if they do not presenting any
understandings of DL.

Improper DL corner case handling is one of the root cause of DL
vulnerabilities due to the challenge compounded by the complexity of DL
processes and the need for specialized DL knowledge.

Figure 5: Example of PR#1048 for exceptional conditions. Figure 6: Example of
CVE-2021-37689 for coding rules.

Root cause 6: Input/output neutralization. The root cause of such
vulnerability is being unable to guarantee the message flowed as input and
output in the system. Our dataset dominantly originates from the improper
validation of the specified type and quantity of input. Some may be related to
memory and GPU allocation, such as the PR#38417 in TensorFlow [67]. When there
is no GPU in the system, the device tracer should not be created to avoid out-
of-memory. It may happen in the feature extraction stage, i.e.,
‘CVE-2016-1517’ for OpenCV. The attacker can launch remote code execution on
the victim’s machine by injecting an infected image with OpenCV. Moreover, for
DL systems, it would be much more complicated for developers to analyze the
latent attack surface and check that the specified input and output are both
‘safe’.

Unable to neutralize input/output is a major root cause of vulnerability in
DL.

Root cause 7: Improper adherence to coding rules.  The root cause of this
vulnerability refers to not following certain coding rules of development.
Development for DL is a rapidly developing area, for which a significant
amount of code is implemented to deliver the functional and non-functional
requirements. Until now, given the booming programming language and framework
communities for DL, there are no coding standards or rules for developers. In
our dataset, ‘Dead code’, ‘Null Pointer Dereference’ and ‘Reliance on
Uncontrolled Component’, are three main sub-root causes. Figure 6 is an
example of null pointer dereference caused by a crafted TFLite model from
manipulation of the MLIR optimization function of L2NormalizeReduceAxis
operator.

Dead code, null pointer dereference, reliance of uncontrolled component are
the root causes of vulnerabilities due to improper adherence to coding rules.

###  IV-B RQ2: Challenges in Vulnerabilities Detection

To understand RQ2, we go through the dataset focusing on two aspects, the
input to trigger the vulnerabilities (its type, range, and visibility), and
the output and behavior (the impact). It should be noted that, for developers,
figuring out the exact location and performing a specific analysis of the
vulnerability in DL is challenging. However, with the developers discussion
corpus and source code, this is by far the best way to provide us the insight
from our dataset regarding the vulnerability detection challenges in DL
systems.

Challenge 1: DL artifacts testing. While there is a hard-coded relationship
between inputs and outputs in traditional software systems, inclusively and
effectively designing a tool as a test oracle boots the software development
efficiency. However, it is still a challenging task to test the system to
date. Now, with learning and inference capability, DL systems attempt to
extrapolate the relationship from massive data as a core module in the system,
such as Microsoft Outlook and OpenDNS. To achieve a specific function in the
DL systems, the development team faces many more options ranging from data,
features, algorithms, and models. As discussed in Section IV-A, the input and
output in DL systems are highly dynamic and do not present a consistent
pattern. The input could be varied on a case-by-case basis, such as an empty
list (_e.g._ PR#58651 in PyTorch [68]) and a specially crafted XML file input
(_e.g._ CVE-2019-5063). When input flows to a specific model layer, such as
LSTM/GRU layer (_e.g._ CVE-2020-26270), failure to access CUDA in the back-end
results in a query-of-death vulnerability.

On the other hand, DL artifacts are more intrinsically linked to the
infrastructure, projecting the inference and decision into a hierarchical
structure. Even for a securely saved model, it can trigger the ‘Use of
Uninitialized Resource’ vulnerability while building the computation graph
(_e.g._ CVE-2020-26271) or during code execution (_e.g._ CVE-2020-26266).
These model-related behaviors become broader and generate more critical
impacts in terms of the DL system components and vulnerability types,
respectively. It is substantially challenging for developers to determine an
effective DL artifact testing protocol, which refers to the testing oracle in
software. Some works have started investigating issues such as tensor property
[40] and DL operators [53] by expanding the capability of existing test suite
to design novel security test cases. As a significant outcome of the DL
systems vulnerability taxonomy, future research may target a general test
oracle problem of DL systems testing and achieve an automated solution to
deliver the testing process. DL experts can play a pivotal role in testing
design work and provide important definition criteria.

The dynamic input-output relationship and intrinsically link with underlying
infrastructure make it challenges to test DL artifacts.

Challenge 2: Hardware support. Currently, general and specific hardware for DL
system has been complicated since it generates the data in a different form,
such as the sensor data, signal input, middle-ware data flow, and output.
Hardware support is observed to be less likely to be detected, such as CUDA
development kits for GPU support (_e.g._ PR#8246 in PyTorch [69] and PR#633 in
Caffe [70]).

Thus, a developer who has less experience with the hardware will be in a
disadvantageous position when implementing DL systems. In PR#5376 in PyTorch
[71] and PR#42615 in TensorFlow [72], the developers triggered runtime errors
without correct hardware settings and configurations. Specifically, in a
multi-GPU setup, PyTorch will attempt to utilize all GPU hardware for the best
performance. However, this behavior may randomly crash with an Out-of-Memory
error because of an imbalance of computing capability among GPUs. Unlike
PyTorch, TensorFlow is free from such vulnerability because it can
automatically discard those GPUs without sufficient computing capabilities.
However, a callback in DynamicPartitionOpGPU will run outside the correct GPU
context and eventually crash. Although PyTorch can be configured to avoid this
problem, the inaccuracy or insufficient error message points developers in a
wrong debug direction, making it challenging to recognize the vulnerabilities.

The stealthy nature of vulnerabilities linked to hardware support in DL system
complicates the vulnerability detection.

Challenge 3: Domain knowledge. Unlike traditional attacking behavior, one main
goal of attacking a DL system is to introduce malicious data and manipulate
the model behavior, misleading the prediction, clustering or regression
output. The overall DL lifecycle involves a dynamic process of processing raw
data, feature representation, model training, and evaluation, in which the
logic related (see root cause 1, 3, and 5 in § IV-A) and artifact related (see
root cause 2, 6, and 7 in § IV-A vulnerabilities are difficult to discover
using existing techniques. One typical example is from PR#5161 in OpenCV [73],
in which the developer has limited knowledge about convergence algorithms.
Insufficient knowledge of the algorithm in this issue leads to incorrect
implementation and undefined behavior. This type of vulnerability is hard to
detect because developers normally assume that the implementation of the
algorithm is correct. As a widely applied DL algorithm, this vulnerability can
cause a wide range of impacts.

Addressing the challenge of detecting logic-related and artifact-related
vulnerabilities requires a strong foundation in domain knowledges.

Challenge 4: Third-party library support. Like other software, DL systems
relied heavily on third-party libraries. Although these libraries can reduce
the coding effort during development, they introduce significant security
risks. Insufficient understanding of the third-party code might hinder the
vulnerability detection, thus increasing the patching effort.

It refers to the challenge of legitimating the third-party library in use and
installing well-supported in place. In PR#13692 in OpenCV [74], developers
discover a vulnerability related to third-party library compatibility when
aiming to enable an asynchronous external API in OpenCV. However, the support
of FP32 networks is missing on Intel’s Myriad plugin. The first patch actually
introduces a check for the type of inference engine to neutralize the
potential crash. However, this approach dramatically increases the execution
time even generating incorrect results due to running unnecessary tests. After
digging into the details of the external API, a new patch is done to eliminate
this issue by refactoring the execution flow to avoid supernumerary
assertions. To fix the lack of support issues, developers have to patch the
vulnerability twice.

Using third-party libraries in developing DL systems without sufficient
understanding of the code will significantly increase security risks,
presenting challenges for detecting and preventing vulnerabilities.

###  IV-C RQ3: Challenges in Vulnerability Patching

To answer RQ3, we carefully reviewed the available patch and the developers’
discussion in comments to understand the challenges in fixing the DL systems
vulnerabilities. In the meantime, the respective efforts are conducted by
summarizing the line and file changes, discussion comments, and time stamps.
Overall, the goal is to answer RQ3 from two different perspectives: one is
from the difficulty level of the vulnerability patch, and the other is the
response time to close the fix loop. Complete statistical results are included
in our replication package [23]. In this section, we outline the identified
challenges and major findings and propose our supplementary solution to extend
the actionable implications from the basis of the CWE List framework.

Challenge 5: Vulnerability localisation. In the core of CWE List, it conveys a
comprehensive list of individual CWE weaknesses for a range of products, such
as J2EE, ASP.NET, UNIX, and Windows. It also provides developers with
guidelines to facilitate the vulnerability localization and fixing. However,
it remains unclear with the current CWE List for developers to deal with the
vulnerabilities in the DL context. Particularly when the vulnerability is
related to either logic or artifacts aspects, it is difficult for developers
to determine every value and status for every stage during the lifecycle,
while the identical relationship between input and output is a typical way to
localize the vulnerability. Particularly when some additional features are
included to provide benefits for high-performance machine learning model
execution, a simple alteration to invalidate the assumptions could cause
significant security issues (_e.g._ CVE-2022-23594 for TFG dialect of
TensorFlow, and CVE-2022-23588 for Grappler optimizer).

The current CWE List’s guidance on addressing vulnerabilities in the DL
context remains unclear, posing challenges for developers in localizing
vulnerabilities using standard approaches.

Challenge 6: Patching process. Since it has been difficult for developers to
efficiently identify the vulnerability in the collected patches, we observed
the following actions conducted by the developer community. Developers are now
facing much more challenges in the new DL system landscape. Normally, it
includes the actions of vulnerability reproducing, unit testing, and community
involvement during the patching process.

  * •

Unit test: It is still a direct practice in the patch process. In PR#24674
[75] and PR#5349 [76], the developers patched the vulnerabilities along with
the corresponding unit test. Unit testing ensures the quality of the patch and
is easy to debug. In addition, by reviewing the unit test, the reviewers can
quickly understand the context of the vulnerability and its impact. However,
the tasks of adding positive test cases and complete unit tests are non-
trivial, such as CVE-2022-23559 for integer overflow in TFLite.

  * •

Vulnerability reproduction: This is seldom observed in our dataset though it
is a general approach for patching. One typical example following this method
is in PR#36856 [77] and Issue#36692 [78]. The developer recognised a
segmentation fault due to improper padding for convolution operation. The
vulnerability was reported in detail with error logs and codes for
vulnerability reproducing. However, only a limited portion of patches has
followed this practice. It challenges the reviewers to countenance the patch
in a timely manner.

  * •

Community involvement: Providing sufficient community support for the patch
process is critical for vulnerabilities in DL systems. In PR#5585 [79], the
developer patches a memory leak vulnerability due to improper release of file
resources in a multiprocessing case. During the patch process, a few
communities reviewers are involved to raise the questions and pointed out the
patching issues, including typos, potential problems, and possible
optimization. One of the reviewers also questions the necessity of the patch.
Positive involvements of the community can force the developer to get better
understanding of the vulnerability and improve the patch quality despite the
extension of patch time.

Ensuring robust unit testing, accurate vulnerability reproduction, and active
community involvement presents a significant challenge in the effective
identification and resolution of DL vulnerabilities.

Figure 7: CWE pillar to line changed mapping. Figure 8: Top 20 taxonomy to
line changed mapping. Figure 9: DL specific taxonomy (CWE List additional
part).

Supplementary solution for CWE List framework. Following the challenges and
findings, we observed that the current CWE List framework has certain
limitations that could not guarantee the DL systems and frameworks. According
to Figure 7, it is hard to distinguish dedicated efforts for the specific CWE
pillar types in terms of line changes. Thus, we have also included a
supplementary list of vulnerability types in this work. In addiction to the
taxonomy described in Table IV, we introduce the taxonomy of DL specific
vulnerabilities as shown in Figure 9.

The complete taxonomy correlations with the changed lines of code (LOC) are
demonstrated in Figure 8. We can see that the distribution of our dataset
range evenly in terms of LOC, which are categorized into ‘$<$10 lines’, ‘10-99
lines’, ‘100-999 lines’, and ‘1000+ lines’. All vulnerability types except the
top 20 are grouped into Other. According to the result, the top 6
vulnerabilities are Improper Validation of Algorithm Parameters (9.65%),
Improper Validation of Tensor Rank (8.34%), Improper Validation of Tensor Size
(5.90%), Missing Release of Memory after Effective Lifetime (5.48%), Improper
Restriction of Operations within the Bounds of a Memory Buffer (5.10%),
Integer Overflow or Wraparound (4.55%). Three of them are the DL-related types
that come from our proposed taxonomy. It turns out that our fine-grained DL-
specific taxonomy effectively highlights the majority DL-related
vulnerabilities from the conventional DL project. Accompanied by more specific
definitions of DL-related vulnerability, DL developers may easily localize the
DL-related vulnerability and come up with an effective patching solution. More
technical details of the proposed fine-grained DL-specific taxonomy for the
CWE List are included in [23].

##  V Discussion

In this work, we systematically design a two-stream analysis framework
combining a set of regular expression rules to automatically identify latent
vulnerability in DL systems. With the results of the manual analysis, our
framework in Figure 2 achieves an accuracy of 82. 39% on GitHub and a
precision of 99. 03% on the TensorFlow security advisory. It outperforms the
most popular methods for empirical study [57, 58]. Furthermore, we proposed a
supplementary CWE List solution originating from CWE List 4.9 covering seven
pillars and a total 72 different vulnerabilities with an additional taxonomy
as shown in Figure 9.

###  V-A Insights of Our Study

DL-specific vulnerabilities classification.  In addition to the CWE 4.9
classification, we further classify the DL-specific vulnerabilities into DL-
specific concepts such as Tensor, Model, Algorithm, Dataset, and Hardware
(GPU,TPU) as shown in Figure 9. Figure 10 demonstrates the mapping of the CWE
List classification to the corresponding DL-related taxonomy. It provides
further insight into vulnerability in the DL context:

  * •

Improper Validation of Algorithm Parameters (28.03%) and Improper Validation
of Tensor (Size, Dimension, Rank, Shape, Value, Type) (68.95%) are the main
causes covering over 96.98% DL-related vulnerabilities in total.

  * •

Major DL-related vulnerabilities from current CWE List are Improper Validation
of Specified Quantity in Input (24.17%), Improper Input Validation (21.05%),
Divide by Zero (19.30%), Reachable Assertion (9.93%), Null Pointer Dereference
(8.46%), Out-of-Bounds Write (6.25%), Out-of-Bounds Read (4.96%), covering
94.12% vulnerabilities.

Dissecting the vulnerabilities in a DL context offers a deeper understanding
of the root cause and the corresponding fix pattern for these issues. As shown
in Figure 10, improper validation of algorithm parameters (_e.g._ batch size,
channel size, filter size, input or output shape) and tensor properties
(_e.g._ size, dimension, rank, shape, value and type) are the leading causes
of DL related vulnerability. Accordingly, validating these parameters and
tensor properties during development can neutralize the potential issues to
the maximum extent (more than 96. 98% of DL-related problems).

Figure 10: Top 10 CWE to top 10 DL specific taxonomy mapping.

Another finding from our empirical study is that many patches contain only
information on vulnerabilities symptom without pointing out the cause and the
fix method. However, the lack of description for the cause and fix method will
make the patch challenging to review and evaluate by authors or reviewers from
communities. This could potentially reduce patch quality and even cause new
problems. A suggestion for improving coding quality is to clarify the symptom
of the vulnerability, the cause of the issue, and how the patch fixes the
problem.

Weaknesses comparison across DL frameworks.  The cross-checking of
vulnerabilities among five projects is illustrated in Figures 11 and 12. These
vulnerabilities are categorized into seven pillars according to the CWE List.
The pillars include: CWE-664 Resource Control, CWE-682 Incorrect Calculation,
CWE-691 Control Flow, CWE-693 Protection Mechanism, CWE-703 Exceptional
Conditions, CWE-707 Neutralization, and CWE-710 Coding Rules. Based on the
results of the comparison, the resource control issue is the most common
weakness in DL frameworks. TensorFlow and OpenCV handle exceptional conditions
that are vastly superior to others, while Keras faces a large portion of
exceptional issues. Also, TensorFlow and OpenCV almost have no protection
mechanism issue. All frameworks but TensorFlow only have a small portion of
the calculation vulnerability. These phenomena indicate that DL frameworks are
more vulnerable to resource-related weaknesses. Moreover, TensorFlow and
OpenCV might have a better code design and mechanisms to handle exceptions.
Due to the fact that TensorFlow involves massive tensor operations and
algorithm executions, it is more vulnerable to numerical weaknesses.

Figure 11: Percentage of vulnerabilities in each framework. Figure 12:
Distribution of vulnerabilities in each CWE pillar.

Unlike TensorFlow and OpenCV, other frameworks of Keras, Caffe, and PyTorch
have little attention to vulnerability issues. Although in our dataset, no CVE
record is returned for these frameworks, our vulnerability search results show
considerable weaknesses in the repositories. A vulnerability might not
directly influence the system’s usability, but malicious users can mislead the
system for irreversible consequences. The growing applications of DL systems
in production indicate a new futuristic software form. Thus, we echo the
raised concerns on better understanding and managing the DL systems
vulnerability [80, 40]. In particular, documentation of well-maintained
securities advisories such as TensorFlow could be a practical move.
Emphasizing and improving the securities requirements for all community
contributors is also suggested.

Actionable findings.  According to the study, following actionable
implications are concluded to assist developers and researchers to avoid,
handle and mitigate DL vulnerabilities:

  * •

To avoid vulnerability:

    * –

Developers should properly validate the DL-incorporated resources and the
defined elements in code, including the GPU availability, algorithm
parameters, tensor value, type, shape, rank, and dimension. (Root cause 1)

    * –

Developers should properly define the operation to the resources, in which of
the DL systems the major concerns are from data and memory buffer. (Root cause
1)

    * –

Developers should properly handle the range of resources in DL (Double Free,
Use After Free, Out-of-Bounds). (Root cause 1)

    * –

Developers should pay attention to the calculation (wrong calculation, integer
underflow/overflow) as it is sensitive to all the DL training and testing
stages. (Root cause 2)

    * –

Developers should consider the race condition carefully, as DL projects often
involve parallel computing processes using shared GPU, threads, and memory.
(Root cause 3)

    * –

Developers should provide sufficient defense against a protection mechanism
for adversary attacks. (Root cause 4)

    * –

Developers should pay more attention to the corner cases for DL systems. (Root
cause 5)

    * –

Developers should validate the type and quantity of input for neutralization
issues. (Root causee 6)

    * –

Future work may target generalizing DL development coding standards and rules.
(Root cause 7)

  * •

For dealing with DL vulnerability detection:

    * –

Future research may target a general test oracle of DL systems testing and
achieve automation to deliver the testing process. DL experts can play a
pivotal role in testing design and provide essential definition criteria.
(Challenge 1)

    * –

Developers should have sufficient knowledge about DL-related hardware to
detect hardware-related problems (Challenge 2)

    * –

Developers should have sufficient knowledge of algorithms to improve the
implementation quality and reduce the chance of undefined behavior. (Challenge
3)

    * –

Developers should understand the third-party libraries’ code more deeply.
(Challenge 4)

  * •

For patching the vulnerabilities:

    * –

Future research could target to improve CWE List in terms of DL-context to
better localize the vulnerability. (Challenge 5)

    * –

Adding unit tests for DL is nontrivial. Finding an efficient way to conduct
unit tests for DL systems could be a potential research point. (Challenge 6)

    * –

Developers can document the cause, patch methods, and symptoms in detail for
reviewers to reproduce the vulnerability and verify the patching quality.
(Challenge 6)

    * –

Open-source the project can bring in community support and help to detect and
verify the issues. (Challenge 6)

Compared to general software systems, avoiding, detecting and patching
vulnerabilities in DL systems presents a unique challenge due to the complex
nature of DL architectures and the intricate interaction between software and
hardware resources. For example, DL systems are highly sensitive to resource
management issues, such as out-of-bound errors and race conditions, due to
parallel processing and shared resources. Furthermore, the complexity of DL
models means that even minor calculation errors can significantly impact the
outcomes. In addition, as DL systems, they require the ability to defend
against DL-specific vulnerabilities, such as adversarial attacks. Overcoming
these challenges requires DL system developers and researchers to possess a
comprehensive set of skills and knowledge, including a deep understanding of
DL principles, familiarity with hardware, and proficiency in handling high-
dimensional tensors and complex DL algorithms. In addition, the rapid
development nature of DL technology requires ongoing learning and
adaptability, raising the requirement of skills and knowledge to deal with
vulnerabilities in DL systems.

Method versatility. As shown in Figure 2, Our innovative two-stream analysis
framework leverages data from the NVD and GitHub (PRs, Issues, and Commits),
ensuring easy access and adaptability to various open-source projects.
Furthermore, our analysis framework integrates DL-specific concepts, such as
tensors, models, algorithms, datasets, and hardware. This integration provides
a more nuanced, clear, and precise classification of DL-specific
vulnerabilities. Combining a generalized analysis framework with a DL-specific
taxonomy gives our analysis framework superior versatility and seamless
extensibility to a wide variety of DL systems, including transformer and
large-scale language models (LLMs).

###  V-B Threats to Validity

DL Framework Selection.  In our study, we have included the five most popular
DL projects. While the main goal is to represent the vulnerabilities in DL
systems comprehensively, our dataset may not cover all existing DL frameworks,
in particular, we observe that TensorFlow represents the most vulnerabilities
at this stage. In addition, DL frameworks such as CNTK and deeplearning4j are
not included due to limited source code or data availability. In particular,
we carefully select the top five DL projects according to GitHub stars to
mitigate threats, which provides us with a raw dataset of 73,215 closed
issues. To facilitate the investigation of vulnerabilities in DL systems, we
have released the replication package of our work. We anticipate that future
investigation will be covered with more projects.

Vulnerability identification.  To overcome the challenge of the availability
of vulnerabilities, we followed previous studies to collect PR, issues, and
commits. However, the vulnerability identification process may not be
sufficient and can miss some real vulnerability of significant impacts in DL
systems. Although the research methodology is similar in vulnerability
collection for machine learning models for vulnerability detection task, we
have conducted considerable efforts on identifying the vulnerabilities with an
audit process. Future work will be extended with refined regular expressions
for searching.

Manual labeling process.  While two authors are actively involved for manual
analysis, the results could be prone to subjective opinions. In order to
mitigate this threat, statistical analysis and substantial discussions are
conducted for the classification and labeling process. Although the work is
managed independently, the authors support each other with good findings to
build the taxonomy. All of the results with the working code, dataset and
scripts are released for further investigation [23].

##  VI Conclusion

In this work, we present a first systematic study of its kind to better
understand the vulnerabilities of software in DL systems. In particular, we
have innovatively designed a two-stream analysis framework to address the data
source concern, which provides the findings of such root causes and challenges
in the detection and patch process. Ahead of the thought experiments for
vulnerability management in artificial intelligence systems, our empirical
study also includes a supplementary CWE List proposition to provide much more
insights. Following the findings, a summary of actionable implications is
provided for security practice in DL related projects. While we do not provide
strong recommendations for or against, in which the changes for vulnerability
study can be nuanced and also complicated, we believe that this work has
bridged the gap and provided a solid basis for future work to build a secure
guarantee of DL systems.

## References

  * [1] J. Liu, Q. Huang, X. Xia, E. Shihab, D. Lo, and S. Li, “Is using deep learning frameworks free? characterizing technical debt in deep learning frameworks,” in _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Software Engineering in Society_ , 2020, pp. 1–10.
  * [2] Z. Chen, H. Yao, Y. Lou, Y. Cao, Y. Liu, H. Wang, and X. Liu, “An empirical study on deployment faults of deep learning based mobile applications,” in _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 2021, pp. 674–685.
  * [3] Z. Chen, Y. Cao, Y. Liu, H. Wang, T. Xie, and X. Liu, “A comprehensive study on challenges in deploying deep learning based software,” in _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2020, pp. 750–762.
  * [4] Y. Lou, Z. Chen, Y. Cao, D. Hao, and L. Zhang, “Understanding build issue resolution in practice: symptoms and fix patterns,” in _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2020, pp. 617–628.
  * [5] D. Wu, B. Shen, and Y. Chen, “An empirical study on tensor shape faults in deep learning systems,” _arXiv preprint arXiv:2106.02887_ , 2021.
  * [6] J. C. Knight, “Safety critical systems: challenges and directions,” in _Proceedings of the 24th international conference on software engineering_ , 2002, pp. 547–550.
  * [7] C. Wan, S. Liu, H. Hoffmann, M. Maire, and S. Lu, “Are machine learning cloud apis used correctly?” in _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 2021, pp. 125–137.
  * [8] Z. Zhang, Y. Yang, X. Xia, D. Lo, X. Ren, and J. Grundy, “Unveiling the mystery of api evolution in deep learning frameworks a case study of tensorflow 2,” in _2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)_. IEEE, 2021, pp. 238–247.
  * [9] M. J. Islam, G. Nguyen, R. Pan, and H. Rajan, “A comprehensive study on deep learning bug characteristics,” in _Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2019, pp. 510–520.
  * [10] L. Jia, H. Zhong, X. Wang, L. Huang, and X. Lu, “An empirical study on bugs inside tensorflows,” in _Proc. DASFAA_ , 2020, pp. 604–620.
  * [11] M. Yan, J. Chen, X. Zhang, L. Tan, G. Wang, and Z. Wang, “Exposing numerical bugs in deep learning via gradient back-propagation,” in _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2021, pp. 627–638.
  * [12] M. Kim, Y. Kim, and E. Lee, “Denchmark: A bug benchmark of deep learning-related software,” in _2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR)_. IEEE, 2021, pp. 540–544.
  * [13] J. Cao, B. Chen, C. Sun, L. Hu, and X. Peng, “Characterizing performance bugs in deep learning systems,” _arXiv preprint arXiv:2112.01771_ , 2021.
  * [14] M. Nejadgholi and J. Yang, “A study of oracle approximations in testing deep learning libraries,” in _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 2019, pp. 785–796.
  * [15] H. V. Pham, T. Lutellier, W. Qi, and L. Tan, “Cradle: cross-backend validation to detect and localize bugs in deep learning libraries,” in _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_. IEEE, 2019, pp. 1027–1038.
  * [16] Z. Wang, M. Yan, J. Chen, S. Liu, and D. Zhang, “Deep learning library testing via effective model generation,” in _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , 2020, pp. 788–799.
  * [17] D. Wu, D. Gao, E. K. Cheng, Y. Cao, J. Jiang, and R. H. Deng, “Towards understanding android system vulnerabilities: Techniques and insights,” in _Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security_ , 2019, pp. 295–306.
  * [18] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard _et al._ , “$\\{$TensorFlow$\\}$: A system for $\\{$Large-Scale$\\}$ machine learning,” in _12th USENIX symposium on operating systems design and implementation (OSDI 16)_ , 2016, pp. 265–283.
  * [19] Y. Jia, E. Shelhamer, J. Donahue, S. Karayev, J. Long, R. Girshick, S. Guadarrama, and T. Darrell, “Caffe: Convolutional architecture for fast feature embedding,” in _Proceedings of the 22nd ACM international conference on Multimedia_ , 2014, pp. 675–678.
  * [20] G. Bradski and A. Kaehler, _Learning OpenCV: Computer vision with the OpenCV library_. ” O’Reilly Media, Inc.”, 2008.
  * [21] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [22] A. Gulli and S. Pal, _Deep learning with Keras_. Packt Publishing Ltd, 2017.
  * [23] Z. Lai, H. Chen, R. Sun, Y. Zhang, M. Xue, and D. Yuan, “Replication package,” https://github.com/codelzz/Vulnerabilities4DLSystem.
  * [24] Q. Rao and J. Frtunikj, “Deep learning for self-driving cars: Chances and challenges,” in _Proceedings of the 1st International Workshop on Software Engineering for AI in Autonomous Systems_ , 2018, pp. 35–38.
  * [25] Y. Liu and Y.-F. B. Wu, “Fned: a deep network for fake news early detection on social media,” _ACM Transactions on Information Systems (TOIS)_ , vol. 38, no. 3, pp. 1–33, 2020.
  * [26] J. Wang, K. Sun, T. Cheng, B. Jiang, C. Deng, Y. Zhao, D. Liu, Y. Mu, M. Tan, X. Wang _et al._ , “Deep high-resolution representation learning for visual recognition,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 43, no. 10, pp. 3349–3364, 2020.
  * [27] L. M. Cysneiros, M. Raffi, and J. C. S. do Prado Leite, “Software transparency as a key requirement for self-driving cars,” in _2018 IEEE 26th international requirements engineering conference (RE)_. IEEE, 2018, pp. 382–387.
  * [28] J. Bosch, H. H. Olsson, and I. Crnkovic, “Engineering ai systems: A research agenda,” in _Artificial Intelligence Paradigms for Smart Cyber-Physical Systems_. IGI global, 2021, pp. 1–19.
  * [29] A. Nikanjam and F. Khomh, “Design smells in deep learning programs: An empirical study,” in _2021 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 2021, pp. 332–342.
  * [30] G. Giray, “A software engineering perspective on engineering machine learning systems: State of the art and challenges,” _Journal of Systems and Software_ , vol. 180, p. 111031, 2021.
  * [31] E. de Souza Nascimento, I. Ahmed, E. Oliveira, M. P. Palheta, I. Steinmacher, and T. Conte, “Understanding development process of machine learning systems: Challenges and solutions,” in _2019 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM)_. IEEE, 2019, pp. 1–6.
  * [32] M. M. John, H. Holmström Olsson, and J. Bosch, “Architecting ai deployment: A systematic review of state-of-the-art and state-of-practice literature,” in _International Conference on Software Business_. Springer, 2020, pp. 14–29.
  * [33] W. Ye, R. Hu, and M. Enev, “Put deep learning to work: Accelerate deep learning through amazon sagemaker and ml services,” in _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, 2020, pp. 3496–3496.
  * [34] E. M. Malta, S. Avila, and E. Borin, “Exploring the cost-benefit of aws ec2 gpu instances for deep learning applications,” in _Proceedings of the 12th IEEE/ACM International Conference on Utility and Cloud Computing_ , 2019, pp. 21–29.
  * [35] N. Papernot, “A marauder’s map of security and privacy in machine learning: An overview of current and future research directions for making machine learning secure and private,” in _Proceedings of the 11th ACM Workshop on Artificial Intelligence and Security_ , 2018, pp. 1–1.
  * [36] Y. He, G. Meng, K. Chen, X. Hu, and J. He, “Towards security threats of deep learning systems: A survey,” _IEEE Transactions on Software Engineering_ , 2020.
  * [37] I. Evtimov, W. Cui, E. Kamar, E. Kiciman, T. Kohno, and J. Li, “Security and machine learning in the real world,” _arXiv preprint arXiv:2007.07205_ , 2020.
  * [38] H. Chen and M. A. Babar, “Security for machine learning-based software systems: a survey of threats, practices and challenges,” _arXiv preprint arXiv:2201.04736_ , 2022.
  * [39] B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi, and Z. Lin, “When machine learning meets privacy: A survey and outlook,” _ACM Computing Surveys (CSUR)_ , vol. 54, no. 2, pp. 1–36, 2021.
  * [40] N. S. Harzevili, J. Shin, J. Wang, and S. Wang, “Characterizing and understanding software security vulnerabilities in machine learning libraries,” _arXiv preprint arXiv:2203.06502_ , 2022.
  * [41] SEI/CERT, “Cert/cc vulnerability note vu#425163 - machine learning classifiers trained via gradient descent are vulnerable to arbitrary misclassification attack,” https://kb.cert.org/vuls/id/425163, Mar 2020, [Online; accessed 20-Feb-2022].
  * [42] A. A. H. Kim, “The impact of platform vulnerabilities in ai systems,” Ph.D. dissertation, Massachusetts Institute of Technology, 2020.
  * [43] K. Filus and J. Domańska, “Software vulnerabilities in tensorflow-based deep learning applications,” _Computers & Security_, vol. 124, p. 102948, 2023.
  * [44] H. Chen, Y. Zhang, Y. Cao, and J. Xie, “Security issues and defensive approaches in deep learning frameworks,” _Tsinghua Science and Technology_ , vol. 26, no. 6, pp. 894–905, 2021.
  * [45] F. Thung, S. Wang, D. Lo, and L. Jiang, “An empirical study of bugs in machine learning systems,” in _2012 IEEE 23rd International Symposium on Software Reliability Engineering_. IEEE, 2012, pp. 271–280.
  * [46] J. M. Zhang, M. Harman, L. Ma, and Y. Liu, “Machine learning testing: Survey, landscapes and horizons,” _IEEE Transactions on Software Engineering_ , vol. 48, no. 1, pp. 1–36, 2020.
  * [47] Y. Zhang, Y. Chen, S.-C. Cheung, Y. Xiong, and L. Zhang, “An empirical study on tensorflow program bugs,” in _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2018, pp. 129–140.
  * [48] X. Du, Z. Zheng, L. Ma, and J. Zhao, “An empirical study on common bugs in deep learning compilers,” in _2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE)_. IEEE, 2021, pp. 184–195.
  * [49] X. Xie, J. W. Ho, C. Murphy, G. Kaiser, B. Xu, and T. Y. Chen, “Testing and validating machine learning classifiers by metamorphic testing,” _Journal of Systems and Software_ , vol. 84, no. 4, pp. 544–558, 2011.
  * [50] N. Christou, D. Jin, V. Atlidakis, B. Ray, and V. P. Kemerlis, “$\\{$IvySyn$\\}$: Automated vulnerability discovery in deep learning frameworks,” in _32nd USENIX Security Symposium (USENIX Security 23)_ , 2023, pp. 2383–2400.
  * [51] Z. Wang, H. You, J. Chen, Y. Zhang, X. Dong, and W. Zhang, “Prioritizing test inputs for deep neural networks via mutation analysis,” in _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_. IEEE, 2021, pp. 397–409.
  * [52] X. Zhang, N. Sun, C. Fang, J. Liu, J. Liu, D. Chai, J. Wang, and Z. Chen, “Predoo: precision testing of deep learning operators,” in _Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis_ , 2021, pp. 400–412.
  * [53] X. Zhang, J. Liu, N. Sun, C. Fang, J. Liu, J. Wang, D. Chai, and Z. Chen, “Duo: Differential fuzzing for deep learning operators,” _IEEE Transactions on Reliability_ , vol. 70, no. 4, pp. 1671–1685, 2021.
  * [54] MITRE, “Cwe list version 4.9,” https://cwe.mitre.org/data/published/cwe_v4.9.pdf, 2022.
  * [55] ——, “Cve,” https://cve.mitre.org/, 2022.
  * [56] NVD, “National vulnerability database,” https://nvd.nist.gov/vuln/, 2022.
  * [57] A. Bosu, J. C. Carver, M. Hafiz, P. Hilley, and D. Janni, “Identifying the characteristics of vulnerable code changes: An empirical study,” in _Proceedings of the 22nd ACM SIGSOFT international symposium on foundations of software engineering_ , 2014, pp. 257–268.
  * [58] Y. Zhou and A. Sharma, “Automated identification of security issues from commit messages and bug reports,” in _Proceedings of the 2017 11th joint meeting on foundations of software engineering_ , 2017, pp. 914–919.
  * [59] GitHub, “Github security advisory,” https://github.com/advisories/, 2022.
  * [60] J. A. Holton, “The coding process and its challenges,” _The Sage handbook of grounded theory_ , vol. 3, pp. 265–289, 2007.
  * [61] M. Banerjee, M. Capozzoli, L. McSweeney, and D. Sinha, “Beyond kappa: A review of interrater agreement measures,” _Canadian journal of statistics_ , vol. 27, no. 1, pp. 3–23, 1999.
  * [62] TensorFlow, “Philoxrandom: Fix race in gpu fill function,” https://github.com/tensorflow/tensorflow/pull/10298, 2017.
  * [63] Keras, “Model generators: Make sure all threads finish when stop is requested,” https://github.com/keras-team/keras/pull/5049, 2017.
  * [64] PyTorch, “Don’t throw exceptions inside openmp parallel block,” https://github.com/pytorch/pytorch/pull/4857, 2018.
  * [65] Keras, “training.py _check_loss_and_target_compatibility fix crash if y is none,” https://github.com/keras-team/keras/pull/7071, 2018.
  * [66] Caffe, “Conv layer: fix crash by setting weight pointer,” https://github.com/BVLC/caffe/pull/1048, 2014.
  * [67] TensorFlow, “r2.2-rc3 cherry-pick request: Fix a bug that profile xla gpu crashes oom,” https://github.com/tensorflow/tensorflow/pull/38417, 2020.
  * [68] PyTorch, “Onnx fix the issue of converting empty list to sequence,” https://github.com/pytorch/pytorch/pull/58651, 2021.
  * [69] ——, “Hotfix: Fix test_cuda import in test_cuda,” https://github.com/pytorch/pytorch/pull/8246, 2018.
  * [70] Caffe, “Support cpu only memcpy,” https://github.com/BVLC/caffe/pull/633, 2014.
  * [71] PyTorch, “Dataparallel: Gpu imbalance warning,” https://github.com/pytorch/pytorch/pull/5376, 2018.
  * [72] TensorFlow, “Fix dynamicpartitionopgpu when running on multiple gpus,” https://github.com/tensorflow/tensorflow/pull/42615, 2020.
  * [73] OpenCV, “fix some functions for valid processing of empty string content,” https://github.com/opencv/opencv/pull/5161, 2019.
  * [74] ——, “Remove assert_any_throw tests for myriad plugin,” https://github.com/opencv/opencv/pull/13692, 2019.
  * [75] TensorFlow, “Tftrt: Support dilated convolutions,” https://github.com/tensorflow/tensorflow/pull/24674, 2019.
  * [76] ——, “Include libcurl into the bazel build,” https://github.com/tensorflow/tensorflow/pull/5349, 2016.
  * [77] ——, “Tflite fix for the segmentation fault. when quantize conv_2d with dilation 1̄,” https://github.com/tensorflow/tensorflow/pull/36856, 2020.
  * [78] ——, “Tfliteconverter segmentation fault when dilation is not (1,1) in conv_2d,” https://github.com/tensorflow/tensorflow/issues/36692, 2020.
  * [79] PyTorch, “Fix memory leak when using multiple workers on window,” https://github.com/pytorch/pytorch/pull/5585, 2018.
  * [80] J. M. Spring, A. Galyardt, A. D. Householder, and N. VanHoudnos, “On managing vulnerabilities in ai/ml systems,” in _New Security Paradigms Workshop 2020_ , 2020, pp. 111–126.


11institutetext: Shamoon College of Engineering, Beer-Sheva 84100, Israel
11email<EMAIL_ADDRESS>22institutetext: Department of Computer Science,
Ben-Gurion University, Beer-Sheva 84105, Israel
22email<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>
# Piercing Diametral Disks Induced by Edges of Maximum Spanning Tree ††thanks:
This work was partially supported by Grant 2016116 from the United States –
Israel Binational Science Foundation.

A. Karim Abu-Affash 11 Paz Carmi 22 Meytal Maman 22

###### Abstract

Let $P$ be a set of points in the plane and let $T$ be a maximum-weight
spanning tree of $P$. For an edge $(p,q)$, let $D_{pq}$ be the diametral disk
induced by $(p,q)$, i.e., the disk having the segment $\overline{pq}$ as its
diameter. Let ${{\cal{D}}}_{T}$ be the set of the diametral disks induced by
the edges of $T$. In this paper, we show that one point is sufficient to
pierce all the disks in ${{\cal{D}}}_{T}$, thus, the set ${{\cal{D}}}_{T}$ is
Helly. Actually, we show that the center of the smallest enclosing circle of
$P$ is contained in all the disks of ${{\cal{D}}}_{T}$, and thus the piercing
point can be computed in linear time.

###### Keywords:

Maximum spanning tree Piercing set Helly’s Theorem Fingerhut’s Conjecture.

##  1 Introduction

Let $P$ be a set of points in the plane and let $G=(P,E)$ be the complete
graph over $P$. A _maximum-weight spanning tree_ $T$ of $P$ is a spanning tree
of $G$ with maximum edge weight, where the weight of an edge $(p,q)\in E$ is
the Euclidean distance between $p$ and $q$, and denoted by $|pq|$. For an edge
$(p,q)$, let $D_{pq}$ denote the _diametral_ disk induced by $(p,q)$, i.e.,
the disk having the segment $\overline{pq}$ as its diameter. Let
${{\cal{D}}}_{T}$ be the set of the diametral disks obtained by the edges of
$T$, i.e., ${{\cal{D}}}_{T}=\\{D_{pq}\ :\ (p,q)\in E_{T}\\}$, where $E_{T}$ is
the set of the edges of $T$. In this paper, we prove that the disks in
${{\cal{D}}}_{T}$ have a non-empty intersection.

###  1.1 Related works

Let ${{\cal{F}}}$ be a set of geometric objects in the plane. A set $S$ of
points in the plane _pierces_ ${{\cal{F}}}$ if every object in ${{\cal{F}}}$
contains a point of $S$, in this case, we say that $S$ is a _piercing set_ of
${{\cal{F}}}$. The piercing problem, i.e., finding a minimum cardinality set
$S$ that pierces a set of geometric objects, has attracted researchers for the
past century.

A famous result is Helly’s theorem [7, 8], which states that for a set
${{\cal{F}}}$ of convex objects in the plane, if every three objects have a
non-empty intersection, then there is one point that pierces all objects in
${{\cal{F}}}$. The problem of piercing pairwise intersecting objects has been
also studied, particularly when the objects are disks in the plane. It has
been proven by Danzer [4] and by Stacho [11, 12] that a set of pairwise
intersecting disks in the plane can be pierced by four points. However, these
proofs are involved and it seems that they can not lead to an efficient
algorithm. Recently, Har-Peled et al. [6] showed that every set of pairwise
intersecting disks in the plane can be pierced by five points and gave a
linear time algorithm for finding these points. Carmi et al. [2] improved this
result by showing that four points are always sufficient to pierce any set of
pairwise intersecting disks in the plane, and also gave a linear time
algorithm for finding these points.

In 1995, Fingerhut [5] conjectured that for any maximum-weight perfect
matching $M=\\{(a_{1},b_{1}),(a_{2},b_{2}),\dots,(a_{n},b_{n})\\}$ of $2n$
points in the plane, there exists a point $c$, such that
$|ca_{i}|+|cb_{i}|\leq\alpha\cdot|a_{i}b_{i}|$, for every $1\leq i\leq n$,
where $\alpha=\frac{2}{\sqrt{3}}$. That is, the set of the ellipses $E_{i}$
with foci at $a_{i}$ and $b_{i}$, and contains all the points $x$, such that
$|a_{i}x|+|xb_{i}|\leq\frac{2}{\sqrt{3}}\cdot|a_{i}b_{i}|$, have a non-empty
intersection. Recently, Bereg et al. [1] considered a variant of this
conjecture. They proved that there exists a point that pierces all the disks
whose diameters are the edges of $M$. The proof is accomplished by showing
that the set of disks is Helly, i.e., for every three disks there is a point
in common.

###  1.2 Our contribution

A common and natural approach to prove that all the disks in ${{\cal{D}}}_{T}$
have a non-empty intersection is using Helly’s Theorem, i.e., to show that
every three disks have a non-empty intersection. However, we use a different
approach and show that all the disks in ${{\cal{D}}}_{T}$ have a non-empty
intersection by characterizing a specific point that pierces all the disks in
${{\cal{D}}}_{T}$. More precisely, we prove the following theorem.

###### Theorem 1.1

Let ${{\cal{C}}}^{*}$ be the smallest enclosing circle of the points of $P$
and let $c^{*}$ be its center. Then, $c^{*}$ pierces all the disks in
${{\cal{D}}}_{T}$.

This approach is even stronger since it implies a linear-time algorithm for
finding the piercing point, using Megiddo’s linear-time algorithm [9] for
computing the smallest enclosing circle of $P$.

The result in this paper can be considered as a variant of Fingerhut’s
Conjecture. That is, for a maximum-weight spanning tree (instead of a maximum-
weight perfect matching) and $\alpha=\sqrt{2}$ (instead of
$\alpha=\frac{2}{\sqrt{3}}$) the conjecture holds.

##  2 Preliminaries

Let $P$ be a set of points in the plane, let $T$ be a maximum-weight spanning
tree of $P$, and let ${{\cal{D}}}_{T}$ be the set of the diametral disks
induced by the edges of $T$. Let ${{\cal{C}}}^{*}$ be the smallest enclosing
circle of the points of $P$, and let $r^{*}$ and $c^{*}$ be its radius and its
center, respectively. We assume, w.l.o.g., that $r^{*}=1$ and $c^{*}$ is
located at the origin $(0,0)$. Let ${{\cal{D}}}^{*}$ be the disk having
${{\cal{C}}}^{*}$ as its boundary. Let $A_{1}$, $A_{2}$, $A_{3}$, and $A_{4}$
(resp., $Q_{1}$, $Q_{2}$, $Q_{3}$, and $Q_{4}$) be the four arcs (resp., the
four quarters) obtained by dividing ${{\cal{C}}}^{*}$ (resp.,
${{\cal{D}}}^{*}$) by the $x$ and the $y$-axis; see Figure 1 for an
illustration.

###### Lemma 1

Each one of the arcs $A_{1}$ and $A_{3}$ contains at least one point of $P$ or
each one of the arcs $A_{2}$ and $A_{4}$ contains at least one point of $P$.

###### Proof

By definition, there are at least two points of $P$ on ${{\cal{C}}}^{*}$. If
there are exactly two points $p$ and $q$ on ${{\cal{C}}}^{*}$, then the
segment $\overline{pq}$ is a diameter of ${{\cal{C}}}^{*}$, and clearly, $p$
and $q$ are on non-adjacent arcs of ${{\cal{C}}}^{*}$; see Figure 1(a).
Otherwise, there are at least three points of $P$ on ${{\cal{C}}}^{*}$; see
Figure 1(b,c). In this case, there are three points $p$, $q$, and $t$ on
${{\cal{C}}}^{*}$, such that the triangle $\triangle pqt$ contains $c^{*}$.
Thus, every angle in this triangle is acute, and therefore two points from
$p,q,t$ are on non-adjacent arcs of ${{\cal{C}}}^{*}$.

Figure 1: The smallest enclosing circle ${{\cal{C}}}^{*}$ of $P$. (a) Two
points on ${{\cal{C}}}^{*}$. (b) and (c) Three points on ${{\cal{C}}}^{*}$.

###### Lemma 2

Let $p$ and $q$ be two points in $Q_{3}$, such that $p$ is on the negative
$x$-axis, the angle $\angle pc^{*}q<\frac{\pi}{2}$, and
$|c^{*}p|\geq|c^{*}q|$; see Figure 2. Then,

  * (i)

for every point $t$ on $A_{1}\cup A_{2}$, we have $|qt|>|pq|$,

  * (ii)

for every point $t$ on $A_{1}\cup A_{4}$, we have $|pt|>|pq|$, and

  * (iii)

for every two points $t$ and $t^{\prime}$ on $A_{2}$ and $A_{4}$,
respectively, we have $|tt^{\prime}|>|pq|$.

###### Proof

  * (i)

Let $a$ and $b$ be the intersection points of ${{\cal{C}}}^{*}$ with the
negative and the positive $x$-axis, respectively; see Figure 2(a). Let $D_{q}$
be the disk with center $q$ and radius $|qa|$. Since $|c^{*}q|\leq|c^{*}p|$,
we have $\angle c^{*}pq\leq\angle c^{*}qp$, and thus $\angle
c^{*}pq\leq\frac{\pi}{2}$. Hence, $\angle qpa>\frac{\pi}{2}$, and thus
$|qa|>|qp|$. Let $q^{\prime}$ be the intersection point of the line passing
through $a$ and $q$ with the $y$-axis, and let $D_{q^{\prime}}$ be the disk
with center $q^{\prime}$ and radius $|q^{\prime}a|$; see Figure 2(a). Since
$D_{q^{\prime}}$ intersects ${{\cal{C}}}^{*}$ at the points $a$ and $b$, the
arc $A_{1}\cup A_{2}$ is outside $D_{q^{\prime}}$ (this is correct for every
disk centered at a point $x$ on the negative $y$-axis and has a radius
$|xa|$). Thus, for every point $t$ on $A_{1}\cup A_{2}$, we have
$|q^{\prime}t|\geq|qa|$. Since $D_{q}$ is contained in $D_{q^{\prime}}$, this
is also correct for $D_{q}$. Therefore, for every point $t$ on $A_{1}\cup
A_{2}$, we have $|qt|\geq|qa|>|qp|$.

Figure 2: Illustration of the proof of Lemma 2. (a) Any point $t$ on
$A_{1}\cup A_{2}$ satisfies $|qt|>|pq|$. (b) Any point $t$ on $A_{1}\cup
A_{4}$ satisfies $|pt|>|pq|$.

  * (ii)

Let $a$ and $b$ be the intersection points of ${{\cal{C}}}^{*}$ with the
negative and the positive $y$-axis, respectively; see Figure 2(b). Let $D_{p}$
be the disk centered at $p$ with radius $|pa|$. Hence, $D_{p}$ contains
$Q_{3}$, and thus for every point $z\in Q_{3}$, we have $|pz|<|pa|$,
particularly $|pq|<|pa|$. Since $D_{p}$ intersects ${{\cal{C}}}^{*}$ at the
points $a$ and $b$, the arc $A_{1}\cup A_{4}$ is outside $D_{p}$ (this is
correct for every disk centered at a point $x$ on the negative $x$-axis and
has a radius $|xa|$). Therefore, for every point $t$ on $A_{1}\cup A_{4}$, we
have $|pt|>|pa|>|pq|$.

  * (iii)

Since $\angle pc^{*}q<\frac{\pi}{2}$, we have $|pq|<\sqrt{2}$. Moreover, by
the location of $t$ and $t^{\prime}$, we have $|tt^{\prime}|\geq\sqrt{2}$.
Therefore, $|tt^{\prime}|>|pq|$.

Notice that Lemma 2 holds for every two points $p$ and $q$ inside
${{\cal{C}}}^{*}$, such that $\angle pc^{*}q<\frac{\pi}{2}$. This is true
since we can always rotate the points of $P$ around $c^{*}$ (and reflect them
with respect to the $x$-axis if needed) until the farthest point from $c^{*}$
among $p$ and $q$ lays on the negative $x$-axis and the other point lays
inside $Q_{3}$.

###### Corollary 1

Lemma 2 holds for every two points $p$ and $q$ inside ${{\cal{C}}}^{*}$, such
that $\angle pc^{*}q<\frac{\pi}{2}$.

##  3 Proof of Theorem 1.1

Let $G=(P,E)$ be the complete graph over $P$ and let $T=(P,E_{T})$ be the
maximum-weight spanning tree of $P$ (i.e., of $G$). A maximum-weight spanning
tree can be computed by Kruskal’s algorithm [3] (or by the algorithm provided
by Monma et al. [10]) which uses the fact that for any cycle $C$ in $G$, if
the weight of an edge $e\in C$ is less than the weight of each other edge in
$C$, then $e$ cannot be an edge in any maximum-weight spanning tree of $P$.
Kruskal’s algorithm works as follows. It sorts the edges in $E$ in non-
increasing order of their weight, and then goes over these edges in this order
and adds an edge $(p,q)$ to $E_{T}$ if it does not produce a cycle in $T$.
Based on this fact, we prove that for every edge $(p,q)\in E_{T}$, the disk
$D_{pq}$ contains $c^{*}$. More precisely, we prove that for each edge
$(p,q)\in E_{T}$ the angle $\angle pc^{*}q$ is at least $\frac{\pi}{2}$.

###### Lemma 3

For every edge $(p,q)\in E_{T}$, we have $\angle pc^{*}q\geq\frac{\pi}{2}$.

###### Proof

Let $(p,q)$ be an edge in $E_{T}$. We show that if $\angle
pc^{*}q<\frac{\pi}{2}$, then there is a cycle in $G$ in which the edge $(p,q)$
has the minimum weight among the edges of this cycle, and thus $(p,q)$ can not
be in a maximum-weight spanning tree of $P$. Assume towards a contradiction
that $\angle pc^{*}q<\frac{\pi}{2}$, and assume, w.l.o.g., that $p$ and $q$
are in $Q_{3}$, $p$ is on the $x$-axis, and $|c^{*}p|>|c^{*}q|$. We
distinguish between two cases:

  * (i)

If there is a point $t$ on $A_{1}$, then, by Lemma 2, we have $|tp|>|pq|$ and
$|tq|>|pq|$. Thus, the edges $(t,p)$, $(p,q)$, and $(q,t)$ form a cycle and
the edge $(p,q)$ has a weight less than the weight of each other edge in this
cycle; see Figure 3(a). This contradicts that $(p,q)\in E_{T}$.

  * (ii)

Otherwise, by Lemma 1, there exist two points $t$ and $t^{\prime}$ on $A_{2}$
and $A_{4}$, respectively. By Lemma 2, we have $|tq|>|pq|$,
$|t^{\prime}p|>|pq|$ and $|tt^{\prime}|>|pq|$. Thus, the edges
$(t,t^{\prime})$, $(t^{\prime},p)$, $(p,q)$, and $(q,t)$ form a cycle and the
edge $(p,q)$ has a weight less than the weight of each other edge in this
cycle; see Figure 3(b). This contradicts that $(p,q)\in E_{T}$.

Figure 3: Illustration of the proof of Lemma 3. (a) $(p,q)$ is of minimum
weight in the cycle $<t,p,q>$. (b) $(p,q)$ is of minimum weight in the cycle
$<t,p,q,t^{\prime}>$.

##  4 Conclusion

In this paper, we have shown that the diametral disks obtained by the edges of
a maximum-weight spanning tree of a set of points $P$ have a non-empty
intersection. We showed that the disks can be pierced by the center of the
smallest enclosing circle of $P$, which can be computed in linear time [9].

Fingerhut [5] conjectured that for any maximum-weight perfect matching
$M=\\{(a_{1},b_{1}),(a_{2},b_{2}),\dots,(a_{n},b_{n})\\}$ of $2n$ points in
the plane, the set of the ellipses $E_{i}$ with foci at $a_{i}$ and $b_{i}$,
and contains all the points $x$, such that
$|a_{i}x|+|xb_{i}|\leq\alpha\cdot|a_{i}b_{i}|$, for every $1\leq i\leq n$,
where $\alpha=\frac{2}{\sqrt{3}}$, have a non-empty intersection. The smallest
known value for $\alpha$ is $\alpha=\sqrt{2}$, which was provided by Bereg et
al. [1].

In this paper, we considered a variant of Fingerhut’s Conjecture for maximum-
weight spanning tree instead of maximum-weight perfect matching. We showed
that for any maximum-weight spanning tree $T$ and $\alpha=\sqrt{2}$, there
exists a point $c^{*}$, such that for every edge $(a,b)$ in $T$,
$|c^{*}a|+|c^{*}b|\leq\alpha\cdot|ab|$. In Figure 4(a), we show an example of
a maximum-weight spanning tree, such that for any
$\alpha<\frac{1+\sqrt{3}}{2}$, the conjecture does not hold. This provides a
lower bound on $\alpha$. Moreover, in Figure 4(b), we show an example of a
maximum-weight spanning tree for which the center $c^{*}$ of the smallest
enclosing circle does not satisfy the inequality for
$\alpha=\frac{1+\sqrt{3}}{2}$. This means that our approach does not work for
$\alpha=\frac{1+\sqrt{3}}{2}$, but does not mean that the conjecture does not
hold for $\alpha=\frac{1+\sqrt{3}}{2}$. Even though the gap between
$\sqrt{2}\approx 1.414$ and $\frac{1+\sqrt{3}}{2}\approx 1.366$ is very small,
it is an interesting open question to find the exact value for $\alpha$ for
which the conjecture holds.

Figure 4: A maximum-weight spanning tree of the points $\\{a,b,c,d\\}$ (red
edges) and $\alpha=\frac{1+\sqrt{3}}{2}$. (a) The ellipses defined by the
edges $(a,b)$ and $(c,d)$ are tangent to each other. (b) The ellipse defined
by the edge $(a,b)$ does not contain the point $c^{*}$.

## References

  * [1] S. Bereg, O. Chacón-Rivera, D. Flores-Peñaloza, C.Huemer, P. Pérez-Lantero, and C. Seara.  On maximum-sum matchings of points.  CoRR, abs/1911.10610, 2019.
  * [2] P. Carmi, M. J. Katz, and P. Morin.  Stabbing pairwise intersecting disks by four points.  CoRR, abs/1812.06907, 2018.
  * [3] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Introduction to Algorithms, 3rd edition.  The MIT Press, 2009.
  * [4] L. Danzer.  Zur lösung des Gallaischen problems über kreisscheiben in der Euklidischen ebene.  Studia Sci. Math. Hungar, 21(1-2):111–134, 1986.
  * [5] D. Eppstein.  Geometry junkyard.  URL: https://www.ics.uci.edu/~eppstein/junkyard/maxmatch.html.
  * [6] S. Har-Peled, H. Kaplan, W. Mulzer, L. Roditty, P. Seiferth, M. Sharir, and M. Willert.  Stabbing pairwise intersecting disks by five points.  Discrete Math., 344(7):112403, 2021.
  * [7] E. Helly.  Über mengen konvexer körper mit gemeinschaftlichen punkten.  Jahresber. Dtsch. Math.-Ver., 32:175–176, 1923.
  * [8] E. Helly.  Über systeme von abgeschlossenen mengen mit gemeinschaftlichen punkten.  Monatshefte Math., 37(1):281–302, 1930.
  * [9] N. Megiddo.  Linear-time algorithms for linear programming in $\mathbb{R}^{3}$ and related problems.  SIAM J. Comput., 12(4):759–776, 1983.
  * [10] C. Monma, M. Paterson, S. Suri, and F. Yao.  Computing Euclidean maximum spanning trees.  Algorithmica, 5(1-4):407–419, 1990.
  * [11] L. Stacho.  Über ein problem für kreisscheiben familien.  Acta Sci. Math. (Szeged), 26:273–282, 1965.
  * [12] L. Stacho.  A solution of Gallai’s problem on pinning down circles.  Mat. Lapok, 32(1-3):19–47, 1981/84.